In 1993, Agarwal, Pellegrini, and Sharir published a result that would go largely unimproved for over three decades. Their algorithm for counting intersections among $n$ circular arcs of identical radius ran in time $O(n^{4/3 + \epsilon})$—fast, but not quite clean. The $\epsilon$ in that exponent, a small positive constant representing an unavoidable polynomial gap above the $4/3$ barrier, was not a concession to implementation difficulty. It was a theoretical residue: a sign that something in the geometry of unit-radius circles was not yet fully understood.
For most computational geometers, this result functioned as a floor—the starting point for problems that reduced to it—rather than as a ceiling worth pushing against. The three decades of quiet that followed said less about the problem's irrelevance than about its resistance. Circular arc intersection counting underpins operations in robotic path planning, CNC toolpath optimization, architectural tiling generation, and multi-layer interference analysis. It is not an abstract curiosity. It is infrastructure.
Haitao Wang's new paper, set to appear at STACS 2026, finally removes the $\epsilon$. His algorithm achieves a running time of $O(n^{4/3} \log^{16/3} n)$—replacing the polynomial gap with a polylogarithmic factor, and in doing so, narrowing the distance between what theory demands and what algorithms can deliver.
"The improvement reduces the gap between upper and lower bounds from poly($n$) to poly($\log n$)—a new ceiling for what we consider efficient in the processing of unit circular arrangements."
Why Arcs Are Harder Than Segments
The difficulty is geometric and foundational. Two line segments can intersect at most once. Two circular arcs of equal radius can intersect twice. This capacity for double intersection means that the entire apparatus of modern segment intersection counting—developed through years of refinement and recently improved by Chan and Zheng—is not directly applicable. The algorithms that work for lines rely on intersection being a simple, transitive, locally ordereable relation. For arcs, it is not.
Wang's approach is a careful decomposition. Using hierarchical $(1/r)$-cuttings, he partitions the plane into pseudo-trapezoids: cells bounded by vertical walls and circular arc fragments. Within each cell, he categorizes arcs as "long" or "short" relative to the cell's extent, yielding four distinct intersection types to be handled. The most technically delicate is the management of arcs that intersect twice—a case requiring geometric observations about "lunes" (the symmetric difference of two unit disks) and "wedges" defined by arc centers and endpoints. The specificity of the unit-radius constraint is not a limitation here; it is the key that makes these observations sharp.
Sparsity and Practice
For designers and researchers working with unit-circle-based geometries—whether in tile optimization, gear design, or toolpath generation—the practical upshot depends strongly on the density of intersections. When the total intersection count $K$ is small relative to $n$, Wang's algorithm improves further, to $o(n^{4/3})$, allowing sparse arrangements to be processed in near-linear time. This is precisely the regime that matters most in many design applications, where the goal is to verify that a toolpath or a tiling is intersection-free rather than to enumerate a combinatorially explosive set of crossings.
The extension to the bichromatic case—counting intersections between two differently-colored arc sets—has immediate relevance for multi-material printing and collision analysis in layered fabrication, and Wang addresses it within the same framework.
The polylogarithmic factor of $\log^{16/3} n$ is, by Wang's own assessment, unlikely to be tight; further refinement of the exponent is a clear target for future work. But in closing the polynomial gap that has stood since 1993, this paper establishes something important: even in a field as mature as computational geometry, the right geometric insight can unlock a problem that time and compute power alone could not.