Input description: A set of lines and line segments .
Problem description: What is the decomposition of the plane defined by ?
Discussion: One of the most fundamental problems in computational geometry is constructing arrangements of lines, that is, explicitly building the regions formed by the intersections of a set of n lines. Algorithms for a surprising number of problems are based on constructing and analyzing the arrangement of a specific set of lines:
Thinking of geometric problems in terms of the appropriate features in an arrangement can be very useful in formulating algorithms. Unfortunately, it must be admitted that arrangements are not as popular in practice as might be supposed. First, a certain depth of understanding is required to apply them correctly. Second, there have been few available implementations of the fundamental algorithms, a situation that is partially addressed below.
A geometric fact called the zone theorem implies that the kth line inserted cuts through k cells of the arrangement, and further that O(k) total edges form the boundary of these cells. This means that we can scan through each edge of every cell we encounter on our insertion walk, confident that linear total work will be performed while inserting the line into the arrangement. Therefore, the total time to insert all n lines in constructing the full arrangement is .
For example, suppose we are given a set of n points, and we want to know whether any three of them all lie on the same line. This sounds similar to the degeneracy testing problem discussed above. Not only is it similar, it is exactly the same, with only the role of points and lines exchanged. The answer follows from taking our points, dualizing them into lines as above, constructing the arrangement as above, and then searching for a vertex with three lines passing through it. The dual of this vertex gives the line on which the three initial vertices lie.
Once we have constructed an arrangement through incremental methods, it often becomes useful to traverse each face of the arrangement exactly once. Such traversals are called sweepline algorithms and are discussed in some detail in Section . The basic procedure is to sort the intersection points by x-coordinate and then walk from left to right while keeping track of all we have seen.
Implementations: Arrange is a package written in C by Michael Goldwasser for maintaining arrangements of polygons in either the plane or on the sphere. Polygons may be degenerate and hence represent arrangements of lines. A randomized incremental construction algorithm is used and efficient point location on the arrangement supported. Polygons may be inserted but not deleted from the arrangement, and arrangements of several thousand vertices and edges can be constructed in a few seconds. Arrange is available from http://theory.stanford.edu/people/wass/wass.html.
LEDA (see Section ) provides a function that constructs an embedded planar graph from a set of line segments, essentially constructing their arrangement.
Notes: Edelsbrunner [Ede87] provides a comprehensive treatment of the combinatorial theory of arrangements, plus algorithms on arrangements with applications. It is an essential reference for anyone seriously interested in the subject. Good expositions on constructing arrangements include [O'R94].
Arrangements generalize naturally beyond two dimensions. Instead of lines, the space decomposition is defined by planes (or beyond 3-dimensions, hyperplanes). In general dimensions, the zone theorem states that any arrangement of n d-dimensional hyperplanes has total complexity , and any single hyperplane intersects cells of complexity . This provides the justification for the incremental construction algorithm for arrangements. Walking around the boundary of each cell to find the next cell that the hyperplane intersects takes time proportional to the number of cells created by inserting the hyperplane.
The history of the zone theorem has become somewhat muddled, because the original proofs were later found to be in error in higher dimensions. See [ESS93] for a discussion and a correct proof. The theory of Davenport-Schintzl sequences is intimately tied into the study of arrangements. It is presented in [SA95].
The naive algorithm for sweeping an arrangement of lines sorts the intersection points by x-coordinate and hence requires time. The topological sweep [EG89, EG91] eliminates the need to sort, and it traverses the arrangement in quadratic time. This algorithm is readily implementable and can be applied to speed up many sweepline algorithms.
Related Problems: Intersection detection (see page ), point location (see page ).