On the Average Complexity of the k-Level
LetLbe an arrangement ofnlines in the Euclidean plane. Thek-levelofLconsists of all verticesvof the arrangement which have exactlyklines ofLpassing belowv.The complexity (the maximum size) of thek-level in a line arrangement has been widelystudied. In 1998 Dey proved an upper bound ofO(n·(k+ 1)1/3)....
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article in Journal/Newspaper |
| Language: | English |
| Published: |
Carleton University
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/20.500.11850/497066 https://doi.org/10.3929/ethz-b-000464326 |
| Summary: | LetLbe an arrangement ofnlines in the Euclidean plane. Thek-levelofLconsists of all verticesvof the arrangement which have exactlyklines ofLpassing belowv.The complexity (the maximum size) of thek-level in a line arrangement has been widelystudied. In 1998 Dey proved an upper bound ofO(n·(k+ 1)1/3). Due to the correspondencebetween lines in the plane and great-circles on the sphere, the asymptotic bounds carryover to arrangements of great-circles on the sphere, where thek-level denotes the verticesat distancekto a marked cell, thesouth pole. We prove an upper bound ofO((k+ 1)2)on the expected complexity of the(≤k)-level in great-circle arrangements if the south pole is chosen uniformly at random among allcells. We also consider arrangements of great(d−1)-spheres on thed-sphereSdwhichare orthogonal to a set of random points onSd. In this model, we prove that the expectedcomplexity of thek-level is of orderΘ((k+ 1)d−1). In both scenarios, our bounds are independent ofn, showing that the distribution ofarrangements under our sampling methods differs significantly from other methods studiedin the literature, where the bounds do depend onn. ISSN:1920-180X |
|---|