article
The complexity and construction of many faces in arrangements of lines and of segments
published
Herbert
Edelsbrunner
author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833
Leonidas
Guibas
author
Micha
Sharir
author
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).
Springer1990
Discrete & Computational Geometry 10.1007/BF02187784
51161 - 196
yes
Edelsbrunner, H., Guibas, L., & Sharir, M. (1990). The complexity and construction of many faces in arrangements of lines and of segments. <i>Discrete & Computational Geometry</i>, <i>5</i>(1), 161–196. <a href="https://doi.org/ 10.1007/BF02187784">https://doi.org/ 10.1007/BF02187784</a>
Edelsbrunner H, Guibas L, Sharir M. The complexity and construction of many faces in arrangements of lines and of segments. <i>Discrete & Computational Geometry</i>. 1990;5(1):161-196. doi:<a href="https://doi.org/ 10.1007/BF02187784"> 10.1007/BF02187784</a>
H. Edelsbrunner, L. Guibas, M. Sharir, Discrete & Computational Geometry 5 (1990) 161–196.
H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity and construction of many faces in arrangements of lines and of segments,” <i>Discrete & Computational Geometry</i>, vol. 5, no. 1, pp. 161–196, 1990.
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.
Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.” <i>Discrete & Computational Geometry</i> 5, no. 1 (1990): 161–96. <a href="https://doi.org/ 10.1007/BF02187784">https://doi.org/ 10.1007/BF02187784</a>.
Edelsbrunner, Herbert, et al. “The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.” <i>Discrete & Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 161–96, doi:<a href="https://doi.org/ 10.1007/BF02187784"> 10.1007/BF02187784</a>.
40722018-12-11T12:06:46Z2019-04-26T07:22:39Z