---
_id: '4072'
_version: 6
abstract:
- lang: eng
text: We show that the total number of edges ofm faces of an arrangement ofn lines
in the plane isO(m 2/3– n 2/3+2 +n) for any>0. The proof takes an algorithmic
approach, that is, we describe an algorithm for the calculation of thesem faces
and derive the upper bound from the analysis of the algorithm. The algorithm uses
randomization and its expected time complexity isO(m 2/3– n 2/3+2 logn+n logn
logm). If instead of lines we have an arrangement ofn line segments, then the
maximum number of edges ofm faces isO(m 2/3– n 2/3+2 +n (n) logm) for any>0,
where(n) is the functional inverse of Ackermann's function. We give a (randomized)
algorithm that produces these faces and takes expected timeO(m 2/3– n 2/3+2 log+n(n)
log2 n logm).
acknowledgement: The first author is pleased to acknowledge partial support by the
Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation
under Grant CCR-8714565. Work on this paper by the third author has been supported
by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation
Grant DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM
Corporation, and by a research grant from the NCRD-the Israeli National Council
for Research and Development. A preliminary version of this paper has appeared in
theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55.
author:
- first_name: Herbert
full_name: Herbert Edelsbrunner
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas J
last_name: Guibas
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: Edelsbrunner H, Guibas L, Sharir M. The complexity and construction of many
faces in arrangements of lines and of segments. *Discrete & Computational
Geometry*. 1990;5(1):161-196. doi:
10.1007/BF02187784
apa: Edelsbrunner, H., Guibas, L., & Sharir, M. (1990). The complexity and construction
of many faces in arrangements of lines and of segments. *Discrete & Computational
Geometry*, *5*(1), 161–196. https://doi.org/
10.1007/BF02187784
chicago: 'Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity
and Construction of Many Faces in Arrangements of Lines and of Segments.” *Discrete
& Computational Geometry* 5, no. 1 (1990): 161–96. https://doi.org/ 10.1007/BF02187784.'
ieee: H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity and construction
of many faces in arrangements of lines and of segments,” *Discrete & Computational
Geometry*, vol. 5, no. 1, pp. 161–196, 1990.
ista: Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity and construction
of many faces in arrangements of lines and of segments. Discrete & Computational
Geometry. 5(1), 161–196.
mla: Edelsbrunner, Herbert, et al. “The Complexity and Construction of Many Faces
in Arrangements of Lines and of Segments.” *Discrete & Computational Geometry*,
vol. 5, no. 1, Springer, 1990, pp. 161–96, doi:
10.1007/BF02187784.
short: H. Edelsbrunner, L. Guibas, M. Sharir, Discrete & Computational Geometry
5 (1990) 161–196.
date_created: 2018-12-11T12:06:46Z
date_published: 1990-01-01T00:00:00Z
date_updated: 2019-04-26T07:22:39Z
day: '01'
doi: ' 10.1007/BF02187784'
extern: 1
intvolume: ' 5'
issue: '1'
month: '01'
page: 161 - 196
publication: Discrete & Computational Geometry
publication_status: published
publisher: Springer
publist_id: '2053'
quality_controlled: 0
status: public
title: The complexity and construction of many faces in arrangements of lines and
of segments
type: journal_article
volume: 5
year: '1990'
...