The number of edges of many faces in a line segment arrangement Journal Article


Author(s): Aronov, Boris; Edelsbrunner, Herbert; Guibas, Leonidas J; Sharir, Micha
Article Title: The number of edges of many faces in a line segment arrangement
Affiliation
Abstract: We show that the maximum number of edges bounding m faces in an arrangement of n line segments in the plane is O(m2/3n2/3+nα(n)+nlog m). This improves a previous upper bound of Edelsbrunner et al. [5] and almost matches the best known lower bound which is Ω(m2/3n2/3+nα(n)). In addition, we show that the number of edges bounding any m faces in an arrangement of n line segments with a total of t intersecting pairs is O(m2/3t1/3+nα(t/n)+nmin{log m,log t/n}), almost matching the lower bound of Ω(m2/3t1/3+nα(t/n)) demonstrated in this paper.
Journal Title: Combinatorica
Volume: 12
Issue 3
ISSN: 1439-6912
Publisher: Springer  
Date Published: 1992-09-01
Start Page: 261
End Page: 274
DOI: 10.1007/BF01285815
Open access: no