Abstract: This paper presents significant algorithmic advancements for the "many faces" problem in arrangements of lines and segments, a fundamental challenge in computational geometry that had seen little progress for over two decades. By integrating hierarchical cuttings with persistent data structures and refined subproblem solvers, the author achieves new deterministic and randomized time complexity bounds. Specifically, the deterministic algorithm for lines improves upon previous results by a factor of approximately $\log^{2.22} n$. These techniques also extend to the more complex case of line segments and provide a more efficient data structure for face-point location queries.
Introduction
In computational geometry, an arrangement is the partition of the plane formed by a set of $n$ lines or segments. This partition consists of vertices, edges, and faces (the open regions between lines). While a full arrangement of $n$ lines has $O(n^2)$ complexity, many applications—such as motion planning, range searching, and visibility—only require computing specific faces that contain a given set of $m$ points. This is known as the "many faces" problem.
Despite its foundational importance, the deterministic time complexity of this problem had not seen significant improvement since the late 1990s. The primary challenge lies in efficiently "zooming in" on the relevant faces without incurring the $O(n^2)$ cost of computing the entire arrangement.
Algorithmic Framework
The author builds upon the framework established by Agarwal in 1990, introducing several key technical innovations to break the long-standing complexity bottleneck.
Hierarchical Cuttings and Duality
The algorithm utilizes $(1/r)$-cuttings to divide the plane into smaller triangular cells, ensuring that only a fraction of the lines cross any single cell. This divide-and-conquer approach is standard, but the author optimizes the subproblem solvers within these cells. For the line case, the problem is transformed into the dual plane. A face in the primal plane corresponds to the region between the upper and lower hulls of dual point sets.
Persistent Data Structures
To manage the dynamic nature of these hulls during recursive steps, the author employs fully persistent binary search trees (using path-copying). This allows the algorithm to "remember" previous states of the hulls efficiently, avoiding the need to recompute structures when they are modified by split or merge operations. This persistence is essential for reusing geometric structures across different branches of the recursion without the overhead of data duplication.
Handling Segments
The segment case is significantly more complex because faces are not necessarily convex or simply connected. The author employs a recursive strategy that distinguishes between "long" segments (those crossing a cutting cell completely) and "short" segments (those with endpoints inside).
By treating long segments as lines and handling short segments separately, the algorithm eventually merges the results using a fast "blue-red merge" step. This reduction allows the segment case to benefit from the improved line-case subproblem solvers.
Key Results and Complexity
The paper establishes several new bounds that outperform the previous state-of-the-art:
- Line Case (Deterministic): Achieves $O(m^{2/3}n^{2/3} \log^{2/3}(n/\sqrt{m}) + (m+n) \log n)$, improving the previous best by a factor of roughly $\log^{2.22} n$.
- Segment Case (Deterministic): Improves the previous best by a factor of $\log^{2.11} n$.
- Face Queries: Introduces a data structure for point-location queries with $O(n \log n)$ preprocessing time and $O(\sqrt{n} \log n)$ query time—a substantial improvement over the previous $O(n^{3/2} \log^2 n)$ preprocessing requirement.
Conclusion
By refining subproblem solvers and leveraging persistent data structures, this work provides the first major progress on the many faces problem in over twenty years. While these results bring deterministic bounds closer to known lower bounds, future work remains in extending these techniques to 3D arrangements and further closing the optimality gap for all configurations of $m$ and $n$.
Summary updated