DocumentCode
3174977
Title
Combinatorial complexity bounds for arrangements of curves and surfaces
Author
Clarkson, Kenneth L. ; Edelsbrunner, Herbert ; Guibas, Leonidas J. ; Sharir, Micha ; Welzl, Emo
Author_Institution
AT&T Bell Lab., Murray Hill, NJ, USA
fYear
1988
fDate
24-26 Oct 1988
Firstpage
568
Lastpage
579
Abstract
The authors study both the incidence counting and the many-faces problem for various kinds of curves, including lines, pseudolines, unit circles, general circles, and pseudocircles. They also extend the analysis to three dimensions, where they concentrate on the case of spheres, which is relevant for the three-dimensional unit-distance problem. They obtain upper bounds for certain quantities. The authors believe that the techniques they use are of independent interest
Keywords
combinatorial mathematics; computational complexity; combinatorial complexity bounds; curves; general circles; incidence counting; lines; many-faces problem; pseudocircles; pseudolines; spheres; surfaces; three dimensions; three-dimensional unit-distance problem; unit circles; upper bounds; Computer science; Councils; Geometry; Research and development; Shape; Upper bound;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location
White Plains, NY
Print_ISBN
0-8186-0877-3
Type
conf
DOI
10.1109/SFCS.1988.21973
Filename
21973
Link To Document