next up previous contents index CD CD Algorithms
Next: Minkowski Sum Up: Computational Geometry Previous: Motion Planning

Maintaining Line Arrangements



Input description: A set of lines and line segments tex2html_wrap_inline30532 .

Problem description: What is the decomposition of the plane defined by tex2html_wrap_inline30534 ?

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.

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

LEDA (see Section gif) 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 tex2html_wrap_inline30544 , and any single hyperplane intersects cells of complexity tex2html_wrap_inline30546 . 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 tex2html_wrap_inline30548 intersection points by x-coordinate and hence requires tex2html_wrap_inline30550 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 gif), point location (see page gif).    

next up previous contents index CD CD Algorithms
Next: Minkowski Sum Up: Computational Geometry Previous: Motion Planning

Mon Jun 2 23:33:50 EDT 1997