On the Average Complexity of the k-Level
OPEN ACCESS
Author / Producer
Date
2020-10-09
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
11 (1)
Pages / Article No.
493 - 506
Publisher
Carleton University
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
Notes
Funding
171681 - Arrangements and Drawings (ArrDra) (SNF)