Maintaining Line Arrangements

  

 

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:     

• Degeneracy testing - Given a set of n lines in the plane, do any three of them pass through the same point? Brute-force testing of all triples takes time. Instead, we can construct the arrangement of the lines and then walk over each vertex and explicitly count its degree, all in quadratic time.  
• Satisfying the maximum number of linear constraints - Suppose that we are given a set of n linear constraints, each of the form . Which point in the plane satisfies the largest number of them? Construct the arrangement of the lines. All points in any region or cell of this arrangement satisfy exactly the same set of constraints, so we need to test only one point per cell in order to find the global maximum.  

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.

• What do you want to do with the arrangement? - Given an arrangement and a query point, we are often interested in identifying which cell of the arrangement contains the point. This is the problem of point location, discussed in Section . Given an arrangement of lines or line segments, we are often interested in computing all points of intersection of the lines. The problem of intersection detection is discussed in Section .
• How big will your arrangement be? - Algorithms for constructing arrangements are incremental. Beginning with an arrangement of one or two lines, subsequent lines are inserted into the arrangement one at a time, building larger and larger arrangements. To insert a new line, we start on the leftmost cell containing the line and walk over the arrangement to the right, moving from cell to neighboring cell and splitting into two pieces those cells that contain the new line.  

  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 .   

• Does your input consist of points instead of lines? - Although lines and points seem to be different geometric objects, such appearances can be misleading. Through the use of duality transformations, we can turn line L into point p and vice versa:

  

  Duality is important because we can now apply line arrangements to point problems, often with surprising results.   

  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 ).