Arrangements

We start with : line arrangements on the plane. Intuitively, the problem is, given $n$ straight lines on the plane, determine how they partition the plane and how the pieces fit together. (See Figure 3.) Formally, an arrangement consists of cells: 0-dimensional cells called “vertices,” 1-dimensional cells called “edges,” and 2-dimensional cells called “regions” or “faces.”

Suppose we have $n$ lines. How many vertices are there in the arrangement? Well, every two lines will intersect to produce a vertex, so the number is just $^nC_2$. At this point, the reader may object, “What if some lines are parallel or concurrent?” In our discussion, we will consider things to be in “general position.” In this case, we assume that no 2 lines are parallel and no 3 lines are concurrent.

How many edges are there? Each line gets chopped into $n$ edges by the other $n - 1$ lines, so there are $^nC_2$ total edges. How many faces? Each vertex is the bottom vertex of a face. This gives $(^nC_2$) faces. In addition, there are $n + 1$ faces at the bottom of the arrangement that do not have bottom vertices. Therefore, the total number of faces is just $(^nC_2) + n + 1$.

In geometry an arrangement of lines is the partition of the plane formed by a collection of lines. Bounds on the complexity of arrangements have been studied in discrete geometry, and computational geometers have found algorithms for the efficient construction of arrangements.

Figure: A Simple line arrangements.

For any set $A$ of lines in the Euclidean plane, one can define an equivalence relation on the points of the plane according to which two points $p$ and $q$ are equivalent if, for every line $l$ of $A$, either $p$ and $q$ are both on $l$ or both belong to the same open half-plane bounded by $l$. When $A$ is finite or locally finite, the equivalence classes of this relation are of three types:

1. the interiors of bounded or unbounded convex polygons (the cells of the arrangement), the connected components of the subset of the plane not contained in any of the lines of $A$,

2. open line segments and open infinite rays (the edges of the arrangement), the connected components of the points of a single line that do not belong to any other lines of $A$, and

3. single points (the vertices of the arrangement), the intersections of two or more lines of $A$.

These three types of objects link together to form a cell complex covering the plane. Two arrangements are said to be isomorphic or combinatorially equivalent if there is a one-to-one adjacency-preserving correspondence between the objects in their associated cell complexes.