---
_id: '4074'
abstract:
- lang: eng
text: 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.
acknowledgement: The research of the second author was supported by the National Science
Foundation under Grant CCR-8714565. Work by the fourth author has been supported
by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation
Grant No. NSF-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 29th IEEE Symposium on Foundations of Computer Science,
1988.
article_processing_charge: No
article_type: original
author:
- first_name: Kenneth
full_name: Clarkson, Kenneth
last_name: Clarkson
- 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
- first_name: Emo
full_name: Welzl, Emo
last_name: Welzl
citation:
ama: Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. Combinatorial complexity
bounds for arrangements of curves and spheres. Discrete & Computational
Geometry. 1990;5(1):99-160. doi:10.1007/BF02187783
apa: Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., & Welzl, E. (1990).
Combinatorial complexity bounds for arrangements of curves and spheres. Discrete
& Computational Geometry. Springer. https://doi.org/10.1007/BF02187783
chicago: Clarkson, Kenneth, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir,
and Emo Welzl. “Combinatorial Complexity Bounds for Arrangements of Curves and
Spheres.” Discrete & Computational Geometry. Springer, 1990. https://doi.org/10.1007/BF02187783.
ieee: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, “Combinatorial
complexity bounds for arrangements of curves and spheres,” Discrete & Computational
Geometry, vol. 5, no. 1. Springer, pp. 99–160, 1990.
ista: 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.
mla: Clarkson, Kenneth, et al. “Combinatorial Complexity Bounds for Arrangements
of Curves and Spheres.” Discrete & Computational Geometry, vol. 5,
no. 1, Springer, 1990, pp. 99–160, doi:10.1007/BF02187783.
short: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Discrete &
Computational Geometry 5 (1990) 99–160.
date_created: 2018-12-11T12:06:47Z
date_published: 1990-03-01T00:00:00Z
date_updated: 2022-02-17T15:41:04Z
day: '01'
doi: 10.1007/BF02187783
extern: '1'
intvolume: ' 5'
issue: '1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02187783
month: '03'
oa_version: None
page: 99 - 160
publication: Discrete & Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer
publist_id: '2048'
quality_controlled: '1'
status: public
title: Combinatorial complexity bounds for arrangements of curves and spheres
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 5
year: '1990'
...