A Simple Algorithm for Computing the Zone of a Line in an Arrangement of Lines

Abstract

Let $L$ be a set of $n$ lines in the plane. The zone $Z(\ell )$ of a line $\ell$ in the arrangement $\mathcal{A}(L)$ of $L$ is the set of faces of $\mathcal{A}(L)$ whose closure intersects $\ell$. It is known that the combinatorial size of $Z(\ell )$ is $O(n)$. Given $L$ and $\ell$, computing $Z(\ell )$ is a fundamental problem. Linear-time algorithms exist for computing $Z(\ell )$ if $\mathcal{A}(L)$ has already been built, but building $\mathcal{A}(L)$ takes $O(n^2)$ time. On the other hand, $O(n\log n)$-time algorithms are also known for computing $Z(\ell )$ without relying on $\mathcal{A}(L)$, but these algorithms are relatively complicated. In this paper, we present a simple algorithm that can compute $Z(\ell )$ in $O(n\log n)$ time. More specifically, once the sorted list of the intersections between $\ell$ and the lines of $L$ is known, the algorithm runs in $O(n)$ time. A big advantage of our algorithm, which mainly involves a Graham's scan style procedure, is its simplicity.

arXiv commentTo appear in SOSA 2022