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

B. Aronov, H. Edelsbrunner, L. Guibas, M. Sharir, Combinatorica 12 (1992) 261–274.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ;
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.
Publishing Year
Date Published
1992-09-01
Journal Title
Combinatorica
Volume
12
Issue
3
Page
261 - 274
IST-REx-ID

Cite this

Aronov B, Edelsbrunner H, Guibas L, Sharir M. The number of edges of many faces in a line segment arrangement. Combinatorica. 1992;12(3):261-274. doi:10.1007/BF01285815
Aronov, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1992). The number of edges of many faces in a line segment arrangement. Combinatorica, 12(3), 261–274. https://doi.org/10.1007/BF01285815
Aronov, Boris, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir. “The Number of Edges of Many Faces in a Line Segment Arrangement.” Combinatorica 12, no. 3 (1992): 261–74. https://doi.org/10.1007/BF01285815.
B. Aronov, H. Edelsbrunner, L. Guibas, and M. Sharir, “The number of edges of many faces in a line segment arrangement,” Combinatorica, vol. 12, no. 3, pp. 261–274, 1992.
Aronov B, Edelsbrunner H, Guibas L, Sharir M. 1992. The number of edges of many faces in a line segment arrangement. Combinatorica. 12(3), 261–274.
Aronov, Boris, et al. “The Number of Edges of Many Faces in a Line Segment Arrangement.” Combinatorica, vol. 12, no. 3, Springer, 1992, pp. 261–74, doi:10.1007/BF01285815.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar