On the complexity of arrangements of circles in the plane

Citation
N. Alon et al., On the complexity of arrangements of circles in the plane, DISC COM G, 26(4), 2001, pp. 465-492
Citations number
20
Categorie Soggetti
Engineering Mathematics
Journal title
DISCRETE & COMPUTATIONAL GEOMETRY
ISSN journal
01795376 → ACNP
Volume
26
Issue
4
Year of publication
2001
Pages
465 - 492
Database
ISI
SICI code
0179-5376(200112)26:4<465:OTCOAO>2.0.ZU;2-L
Abstract
Continuing and extending the analysis in a previous paper [15], we establis h several combinatorial results on the complexity of arrangements of circle s in the plane. The main results are a collection of partial solutions to t he conjecture that (a) any arrangement of unit circles with at least one in tersecting pair has a vertex incident to at most three circles, and (b) any arrangement of circles of arbitrary radii with at least one intersecting p air has a vertex incident to at most three circles, under appropriate assum ptions on the number of intersecting pairs of circles (see below for a more precise statement).