# Maintaining Line Arrangements

 Input Output

Input Description: A set of lines and line segments $$l_1,...,\l_n$$.
Problem: What is the decomposition of the plane defined by $$l_1,...,\l_n$$?

Excerpt from The Algorithm Design Manual: 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 $$O(n3)$$ 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 $$y less and or equal to ai x + bi$$. 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.

### Related Problems

 Robust Geometric Primitives Intersection Detection Point Location

Go To Main Page