Cutting Circles into Pseudo-Segments and Improved Bounds for Incidences% and Complexity of Many Faces
Cutting Circles into Pseudo-Segments and Improved Bounds for Incidences% and Complexity of Many Faces
复制标题
将%20圆圈%20切割成%20伪线段%20和%20针对%20事件%%20和%20改进了%20边界%20%20的%20许多%20面的复杂性%20
DOI：
10.1007/s00454-001-0084-1
复制
发表时间：
2002
影响因子：
0.8
通讯作者：
M. Sharir
中科院分区：
文献类型：
--
作者：
B. Aronov;M. Sharir
我们证明了平面上的n个任意圆可以被割成O(n3/2+ɛ)条弧，对任意ɛ>；0，使得任何一对弧至多相交一次。这改进了玉木和德山最近的一个结果[20]。利用这一结果，我们得到了m点到n个圆之间关联次数的改进的上界。对于任意常数最大度多项式的图，还得到了一个改进的关联界。
We show that n arbitrary circles in the plane can be cut into O(n3/2+ɛ) arcs, for any ɛ>0 , such that any pair of arcs intersects at most once. This improves a recent result of Tamaki and Tokuyama [20]. We use this result to obtain improved upper bounds on the number of incidences between m points and n circles. An improved incidence bound is also obtained for graphs of polynomials of any constant maximum degree.