---
_id: '4053'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
article_type: original
author:
- first_name: Boris
full_name: Aronov, Boris
last_name: Aronov
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: 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
apa: Aronov, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1992). The number
of edges of many faces in a line segment arrangement. Combinatorica. Springer.
https://doi.org/10.1007/BF01285815
chicago: Aronov, Boris, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir.
“The Number of Edges of Many Faces in a Line Segment Arrangement.” Combinatorica.
Springer, 1992. https://doi.org/10.1007/BF01285815.
ieee: 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. Springer, pp. 261–274, 1992.
ista: 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.
mla: 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.
short: B. Aronov, H. Edelsbrunner, L. Guibas, M. Sharir, Combinatorica 12 (1992)
261–274.
date_created: 2018-12-11T12:06:40Z
date_published: 1992-09-01T00:00:00Z
date_updated: 2022-03-15T15:44:26Z
day: '01'
doi: 10.1007/BF01285815
extern: '1'
intvolume: ' 12'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF01285815
month: '09'
oa_version: None
page: 261 - 274
publication: Combinatorica
publication_identifier:
issn:
- 0209-9683
publication_status: published
publisher: Springer
publist_id: '2074'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The number of edges of many faces in a line segment arrangement
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 12
year: '1992'
...