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.
Original language | English (US) |
---|---|
Pages (from-to) | 261-274 |
Number of pages | 14 |
Journal | Combinatorica |
Volume | 12 |
Issue number | 3 |
DOIs | |
State | Published - Sep 1992 |
Keywords
- AMS subject classification code (1991): 52B05, 52C10, 68U05
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Computational Mathematics