DocumentCode
1710273
Title
On the complexity of many faces in arrangements of circles
Author
Agarwal, Pankaj K. ; Aronov, Boris ; Sharir, Micha
Author_Institution
Dept. of Comput. Sci., Duke Univ., Durham, NC, USA
fYear
2001
Firstpage
74
Lastpage
83
Abstract
We obtain improved bounds on the complexity of m distinct faces in an arrangement of n circles and in an arrangement of n unit circles. The bounds are worst-case tight for unit circles, and, for general circles, they nearly coincide with the best known bounds for the number of incidences between m points and n circles.
Keywords
combinatorial mathematics; computational complexity; computational geometry; best known bounds; circle arrangements; distinct face complexity; general circles; worst-case tight; Application software; Computational geometry; Computer graphics; Computer science; Heart; Information geometry; Information science; Mathematical model; Robots; Solid modeling;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on
Print_ISBN
0-7695-1116-3
Type
conf
DOI
10.1109/SFCS.2001.959882
Filename
959882
Link To Document