---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Kenneth
foaf_name: Clarkson, Kenneth
foaf_surname: Clarkson
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Edelsbrunner, Herbert
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
- foaf_Person:
foaf_givenName: Leonidas
foaf_name: Guibas, Leonidas
foaf_surname: Guibas
- foaf_Person:
foaf_givenName: Micha
foaf_name: Sharir, Micha
foaf_surname: Sharir
- foaf_Person:
foaf_givenName: Emo
foaf_name: Welzl, Emo
foaf_surname: Welzl
bibo_doi: 10.1007/BF02187783
bibo_issue: '1'
bibo_volume: 5
dct_date: 1990^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0179-5376
- http://id.crossref.org/issn/1432-0444
dct_language: eng
dct_publisher: Springer@
dct_title: Combinatorial complexity bounds for arrangements of curves and spheres@
...