--- _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' ...