Feature Column from the AMS

Oriented Matroids: The Power of Unification

3. Arrangements of lines

We are all familiar with lines, line segments, and rays. Lines have no endpoints, segments have two, and rays have one.

Lines divide the plane into a variety of cells (polygonal regions), and one can count the number of sides of the cells. For convenience of the discussion we will assume there are at least 3 lines and we are interested in the case where every pair of lines intersects. Such a collection of lines is known as an arrangement of lines in the plane. If no pair of lines goes through the point of intersection of any other pair of lines, the arrangement is known as a simple arrangement of lines. Some of the regions formed by an arrangement of lines in the Euclidean plane are bounded (i.e. lie completely within some circle), while other regions are unbounded.

Figure 1

The diagram above shows a collection of 5 lines, which you should think of as going off to infinity rather than being line segments. Furthermore, the arrangement above is a simple arrangement which divides the plane into bounded regions with 3 sides, 4 sides, and 5 sides. In fact, there are four 3-gons, one 4-gon, and one 5-gon. How should we treat the unbounded regions? One approach is to think of the two regions labeled R₁ and R₂ as really being the same region. Think of the two lines which form R₂ and move off the top of the diagram as coming back up from the bottom and, thus, defining a region which is the same as R₁. Let us refer to this one region as R. How many sides should we say R has? Since the pieces of R are bounded by 4 lines, it is natural to call R a 4-gon. In this perspective we can think of being involved with a geometry whichlacks parallelism for lines and is known as the (real) projective plane. We have points, lines and the following rules (among others):

a. Two distinct points lie on exactly one line.

b. Two distinct lines pass through exactly one point.

Since the lines in our diagram are being treated as if they have no beginningor end (in contrast to line segments which have two endpoints), the lines behavea bit as if we are thinking of them as "simple curves." In fact, wecan interpret the situation involved as being associated with great circles on the sphere (a great circle of a sphere is one whose center coincides with the center of the sphere). In this interpretation we are thinking of the geometry as being that of the great circles on a sphere, and the points of the geometry are diameter endpoints that have been identified (that is, for each diameter, its two endpoints are thought of as one point).

Returning to arrangements of lines, there is a wide variety of interesting mathematical questions we can address:

a. How many essentially different arrangements and simple arrangements of lines are there with n lines?

b. How few triangular shaped regions can there be in an arrangement of n lines? What is the maximum number of triangular regions there can be in an arrangement of n lines?

c. What is the largest sized region that can occur in an arrangement of n lines?

Note that questions such as these can be asked for arrangements whether they are simple or not. Furthermore, one can look for arrangements with other nice properties such as those in which all the regions formed are triangles. These arrangements are known assimplicial arrangements. Rather surprisingly, in light of how many seeminglydifferent such arrangements have been found, mathematicians are close to beingable to classify all the simplicial arrangements of lines. They fall into severalinfinite classes and many additional "sporadic" arrangements.

However, there are questions about arrangements of lines that do not "scream out" atone as clearly as some of the questions above. For example, concentrate on thecollection S made up of points of intersectionof the lines in Figure 1. There are 10 such points. Now pick any pair of thesepoints and ask how many points in S are on the line determined by the pair ofpoints. It has become standard to refer to such lines, which have precisely twopoints of S on them, as ordinary lines.

So far we have thought of S as arising from intersections of lines in an arrangement of lines. However, suppose we consider any set S* of points (not all on a line) in the plane, which may or may not arise as the set of points where lines in an arrangement meet. Now consider the number of points of S* that lie on each line that is determined by a pair of points in S*. Will there always be such a line with exactly two points on it? This problem, in essence due to J. J. Sylvester and revitalized by Paul Erdös and Tibor Gallai, has been widely explored and has many ramifications.