A Simple Algorithm for Computing the Zone of a Line in an Arrangement of Lines
share
Let L be a set of n lines in the plane. The zone Z(ℓ) of a line ℓ in the arrangement 𝒜(L) of L is the set of faces of 𝒜(L) whose closure intersects ℓ. It is known that the combinatorial size of Z(ℓ) is O(n). Given L and ℓ, computing Z(ℓ) is a fundamental problem. Linear-time algorithms exist for computing Z(ℓ) if 𝒜(L) has already been built, but building 𝒜(L) takes O(n^2) time. On the other hand, O(nlog n)-time algorithms are also known for computing Z(ℓ) without relying on 𝒜(L), but these algorithms are relatively complicated. In this paper, we present a simple algorithm that can compute Z(ℓ) in O(nlog n) time. More specifically, once the sorted list of the intersections between ℓ 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.
READ FULL TEXT