On the Complexity of Arrangements of Circles in the Plane

Noga Alon, Hagit Last, Rom Pinchasi, Micha SharirDiscret. Comput. Geom 2001 · DOI

Introduction

This research addresses a long-standing conjecture in combinatorial geometry regarding the complexity of circle arrangements in the plane. The study provides partial solutions to the question of whether any arrangement of intersecting circles must contain at least one "simple" vertex—an intersection point where no more than three circles meet. By integrating planar graph theory, circle inversion, and advanced range-searching machinery, the authors establish new bounds for both unit circles and arbitrary circles.

The Sylvester–Gallai Analog for Circles

The core of this investigation is a circular extension of the classical Sylvester–Gallai theorem. While the original theorem guarantees that any finite set of points (not all collinear) has a line passing through exactly two of them, the circular version posed by A. Bezdek asks: In a collection of circles where at least two intersect, must there be a vertex incident to only two or three circles?

Proving this is challenging because it is trivial to create a "pencil"—a point where many circles intersect. The difficulty lies in demonstrating that an arrangement cannot avoid low-degree vertices entirely without collapsing into such a pencil configuration.

Methodological Framework: Lenses and Lunes

The authors treat circle arrangements as planar maps and apply Euler’s formula ($V - E + F = 1 + c$) to analyze their structure. A critical component of this analysis involves bounding the number of faces with only two edges, specifically "lenses" and "lunes."

Illustration of a lune and a lens, which serve as proxies for identifying low-degree vertices in an arrangement.
  • Lenses: The intersection of two disks.
  • Lunes: The portion of one disk not covered by another.

The existence of low-degree vertices is intimately tied to these structures. If an arrangement contains few lenses and lunes, it mathematically forces the existence of vertices where only a few circles meet. To handle arbitrary circles, the authors utilize batched range-searching and $\epsilon$-nets to decompose complex arrangements into manageable sub-problems.

Key Insights and Geometric Complexity

The research highlights a significant gap between the behavior of unit circles and circles of arbitrary radii. For unit circles, the number of vertices $V$ is proportional to the number of intersecting pairs $P$ ($V = \Omega(P)$). For arbitrary circles, this relationship only holds under stricter conditions.

A geometric configuration of three circles ($C_1, C_2, C_3$) used to analyze intersection points and vertex degrees.

The authors quantify the "non-pencil-like" nature required to guarantee a simple vertex. For pairwise-intersecting unit circles, they found that the number of lunes is at most 3 and lenses at most $n$. These remarkably small bounds are the primary drivers for the existence of simple vertices.

Key Results

  • Pairwise-Intersecting Arbitrary Circles: For a sufficiently large $n$, if every pair intersects and they do not form a single pencil, there is a vertex incident to $\le 3$ circles.
  • Unit Circle Arrangements: If an arrangement of $n$ unit circles has at least $\beta n$ intersecting pairs (for a constant $\beta$), it must contain a vertex incident to $\le 3$ circles.
  • Complexity Bounds:
    • The number of lenses in an arrangement of $n$ unit circles is $O(n^{4/3} \log n)$.
  • The number of lenses and lunes for arbitrary circles is $O(n^{3/2+\epsilon})$.

Conclusion and Future Directions

While these results represent significant progress, many are asymptotic, requiring $n$ to be "sufficiently large." The original conjecture suggests these properties should hold for any $n > 2$. Furthermore, while the authors achieved a sub-quadratic bound for lenses in unit circle arrangements, they suspect the true bound is near-linear ($O(n)$). Closing this gap and fully resolving the "$\le 3$" conjecture for general arbitrary circles remain open challenges in discrete geometry.

Summary updated

BibTeX
@article{alon2001complexity,
  author = {Noga Alon and Hagit Last and Rom Pinchasi and Micha Sharir},
  title = {{On the Complexity of Arrangements of Circles in the Plane}},
  journal = {Discret. Comput. Geom.},
  year = {2001},
  doi = {10.1007/s00454-001-0043-x},
}

Loading related content...

Figure