On the complexity of arrangements of circles in the plane

N. Alon, H. Last, R. Pinchasi, M. Sharir

Research output: Contribution to journalArticle

18 Scopus citations

Abstract

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).

Original languageEnglish (US)
Pages (from-to)465-492
Number of pages28
JournalDiscrete and Computational Geometry
Volume26
Issue number4
DOIs
StatePublished - Dec 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On the complexity of arrangements of circles in the plane'. Together they form a unique fingerprint.

  • Cite this