INPUT OUTPUT

**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(n*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.^{3})*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 a*. Which point in the plane satisfies the largest number of them? Construct the arrangement of the lines. All points in any region or_{i}x + b_{i}*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.

Davenport-Schinzel sequences and their geometric applications by M. Sharir and P. Agarwal | Computational Geometry in C by Joseph O'Rourke | Algorithms in Combinatorial Geometry by Herbert Edelsbrunner |

This page last modified on 2008-07-10 . www.algorist.com