article
Combinatorial complexity bounds for arrangements of curves and spheres
published
yes
Kenneth
Clarkson
author
Herbert
Edelsbrunner
author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833
Leonidas
Guibas
author
Micha
Sharir
author
Emo
Welzl
author
We present upper and lower bounds for extremal problems defined for arrangements of lines, circles, spheres, and alike. For example, we prove that the maximum number of edges boundingm cells in an arrangement ofn lines is Θ(m 2/3 n 2/3 +n), and that it isO(m 2/3 n 2/3 β(n) +n) forn unit-circles, whereβ(n) (and laterβ(m, n)) is a function that depends on the inverse of Ackermann's function and grows extremely slowly. If we replace unit-circles by circles of arbitrary radii the upper bound goes up toO(m 3/5 n 4/5 β(n) +n). The same bounds (without theβ(n)-terms) hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees in arrangements of lines and of unit-circles our bounds match previous results, but our proofs are considerably simpler than the previous ones. The maximum sum of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m 4/7 n 9/7 β(m, n) +n 2), in general, andO(m 3/4 n 3/4 β(m, n) +n) if no three spheres intersect in a common circle. The latter bound implies that the maximum number of unit-distances amongm points in three dimensions isO(m 3/2 β(m)) which improves the best previous upper bound on this problem. Applications of our results to other distance problems are also given.
Springer1990
eng
Discrete & Computational Geometry
0179-5376
1432-044410.1007/BF02187783
5199 - 160
yes
K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Discrete & Computational Geometry 5 (1990) 99–160.
Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. 1990. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete & Computational Geometry. 5(1), 99–160.
Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., & Welzl, E. (1990). Combinatorial complexity bounds for arrangements of curves and spheres. <i>Discrete & Computational Geometry</i>. Springer. <a href="https://doi.org/10.1007/BF02187783">https://doi.org/10.1007/BF02187783</a>
Clarkson, Kenneth, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Emo Welzl. “Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.” <i>Discrete & Computational Geometry</i>. Springer, 1990. <a href="https://doi.org/10.1007/BF02187783">https://doi.org/10.1007/BF02187783</a>.
K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, “Combinatorial complexity bounds for arrangements of curves and spheres,” <i>Discrete & Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 99–160, 1990.
Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. Combinatorial complexity bounds for arrangements of curves and spheres. <i>Discrete & Computational Geometry</i>. 1990;5(1):99-160. doi:<a href="https://doi.org/10.1007/BF02187783">10.1007/BF02187783</a>
Clarkson, Kenneth, et al. “Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.” <i>Discrete & Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 99–160, doi:<a href="https://doi.org/10.1007/BF02187783">10.1007/BF02187783</a>.
40742018-12-11T12:06:47Z2022-02-17T15:41:04Z