On the complexity of arrangements of circles in the plane

被引：16

作者：

Alon, N ^{[1
]}

Last, H

Pinchasi, R

Sharir, M

机构：

[1] Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel

[2] Hebrew Univ Jerusalem, Inst Math, IL-91904 Jerusalem, Israel

[3] NYU, Courant Inst Math Sci, New York, NY 10012 USA

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2001年 / 26卷 / 04期

关键词：

D O I：

10.1007/s00454-001-0043-x

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Continuing and extending the analysis in a previous paper [15], we establish several combinatorial results on the complexity of arrangements of circles in the plane. The main results are a collection of partial solutions to the conjecture that (a) any arrangement of unit circles with at least one intersecting pair has a vertex incident to at most three circles, and (b) any arrangement of circles of arbitrary radii with at least one intersecting pair has a vertex incident to at most three circles, under appropriate assumptions on the number of intersecting pairs of circles (see below for a more precise statement).

引用

页码：465 / 492

页数：28

共 20 条

[1] ON RANGE SEARCHING WITH SEMIALGEBRAIC SETS [J].