Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

abstract A classical problem in combinatorial geometry is to find a combinatorial characterization of arrangements of hyperplanes (or configurations of points, which are dual to arrangements, as we will see in chapter 1), i.e. establish a scheme that maps the infinite number of arrangements into finitely many classes in such a way that arrangements with the same image can be regarded as equal with respect to some property one is interested in.

J.E.Goodman and R.Pollack \cite{GP80} have given an example which explains the usefulness of such a classification scheme: Let $H(n)$ be the smallest natural number, such that every set of $H(n)$ points in the plane (no three of them collinear) contains the vertices of an empty convex $n$-gon. It is known that $H(5)=10$ \cite{Ha} and that $H(7)$ does not exist \cite{Ho}. Whether $H(6)$ exists, is still an open problem. Suppose you want to attack this question algorithmically and test each configuration of a given number of points whether it contains an empty convex hexagon. Besides from the immense complexity for large configurations, how do you generate all "essentially distinct" configurations? A classification that reflects convexity properties could solve this problem in principle.

In fact, there exists a combinatorial structure that reflects many interesting properties of planar configurations, namely {\it circular sequences}, which were introduced by Perrin \cite{Pe} and treated in detail by Goodman and Pollack \cite{GP80}, \cite{GP84}. An overview is given in \cite{Ed}.

Another representation of $2$-dimensional arrangements was given by Ringel \cite{Ringel}; both approaches work only for nondegenerate arrangements and configurations.

A very powerful and general classification of $d$-dimensional arrangements (which need not even be in general position) in terms of so-called {\it oriented matroids}, was intended by J.Folkman and J.Lawrence \cite{FL} and reproved by A.Mandel \cite{Ma}. A new approach to the 2-dimensional case was given by R.Cordovil \cite{Co}.

It was first observed by Ringel in his thesis that the structure he uses to characterize arrangements of lines actually covers a larger class of arrangements, namely arrangements of {\it pseudolines}, which are topologically similar to straight arrangements. He shows that there are simple arrangements of pseudolines which are not {\it stretchable}, i.e. whose cell complex is not equivalent to that of any arrangement of lines.

Ringel's observation has an equivalent for any combinatorial structure encoding arrangements -- so it seems that straightness cannot be recognized by purely combinatorial means.

In this thesis we develop a characterization of simple $d$-dimensional arrangements of pseudohyperplanes in terms of certain set systems of Vapnik-Chervonenkis dimension $d$. These set systems are called {\it pseudogeometric range spaces} and were introduced by E.Welzl \cite{We}, who has observed that every simple arrangement determines such a range space.

We show that the converse is also true; as a tool, we introduce an interesting new class of range spaces derived from the pseudogeometric spaces, and we characterize both classes by simple maximality conditions. Our techniques are then applied to derive some results on two more topics related to arrangements.

Given a set of hyperplanes $H$ in $d$-space, where one of the open halfspaces of each $h\in H$ is called the {\it positive halfspace} of $h$ (denoted by $h^{+}$), we obtain an {\it arrangement of halfspaces} ${\cal A}(H^{+})$, which consists of the same faces as the underlying arrangement of hyperplanes together with the information, which of the positive halfspaces contain a given point. Now every cell $c$ of the arrangement can be labelled with the set of hyperplanes, whose positive halfspaces contain $c$; the collection of the labels of all cells determines the {\it description of cells} of ${\cal A}(H^{+})$, denoted by ${\cal C}(H^{+})$ (figure \ref{DOC}). Formally, ${\cal C}(H^{+})$ is a pair $(H, R)$, where $H$ is the set of hyperplanes and $R$ a subset of $2^{H}$. Such a pair is called a {\it range space}. We refer to $H$ as the set of {\it elements} of the range space, while $R$ is the set of {\it ranges} of ${\cal C}(H^{+})$.

If the arrangement has at least one vertex, then ${\cal C}(H^{+})$ is a range space of Vapnik-Chervonenkis dimension $d$. Furthermore, if the arrangement is {\it simple} (or in {\it general position}), then ${\cal C}(H^{+})$ reaches the maximum number of ranges that a range space of VC-dimension $d$ can have. Welzl calls a range space with this property {\it complete} of dimension $d$.

Chapter 2 studies complete range spaces and develops their basic properties. Besides from a new concept of {\it range space duality} and a corresponding duality theorem, all the concepts of this chapter are taken directly or in a slightly modified form from an unpublished manuscript of Welzl \cite{We}. Some of them have already appeared in literature.

If we are given a one-dimensional arrangement of halfspaces (i.e. an arrangement of rays on the line), and we connect two ranges of the corresponding description of cells by an edge whenever they differ by a single element, we obtain the {\it distance-1-graph}, which in this case has the structure of a path. In a general complete space of VC-dimension 1 this graph is only a tree, which gives a necessary condition for a complete space to be the description of cells of some arrangement. This necessary condition generalizes to higher dimensions and leads to the definition of {\it pseudogeometric range spaces}, which are the subject of chapter 3 (figure \ref{complete_geom}). The basic properties and characterizations are again taken from \cite{We}.

We prove two theorems motivated by Levi's Enlargement Lemma for arrangements of pseudolines \cite{Le}, \cite{Gr} and newly introduce the concepts of {\it closure} and {\it boundary} of a range space. This leads to an interesting characterization of pseudogemetric spaces by a maximality condition for the number of ranges in the boundary. Furthermore, the duality theorem for complete spaces is shown to hold also for pseudogeometric spaces.

In chapter 4 we discuss a third class of range spaces, called $\overline{PG}$-spaces, which are spaces that arise as the closure of some pseudogeometric space. $\overline{PG}$-spaces can be obtained as the description of cells of so-called {\it arrangements of hemispheres}, and as well as complete and pseudogemetric spaces they can be characterized by a certain maximality condition. Once more a duality theorem is established for $\overline{PG}$-spaces.

In chapter 5 we show that $\overline{PG}$-spaces correspond to simple oriented matroids, and this will lead to a major result of the thesis, namely that $\overline{PG}$-spaces characterize simple {\it arrangements of pseudohemispheres} and pseudogeometric spaces correspond to {\it arrangements of pseudohalfspaces}. The terminolgy and the basic properties of oriented matroids we develop in section 5.2 are taken from \cite{Ma} as well as the formal definitions of arrangements of pseudohemispheres and pseudohalfspaces in section 5.5.

The last two chapters about {\it geometric embeddability} and {\it elementary transformations} of complete range spaces were inspired by conjectures and suggestions of Welzl. These chapters should be seen from the point of view of chapter 5, for they are motivated by properties of arrangements.

Chapter 6 generalizes planarity to range spaces by introducing an embedding scheme that avoids intersections of certain convex hulls. A main motivation for this embeddability concept is the $k$-set problem, and we show how embeddability is related to the $k$-set problem. Furthermore, we characterize the complete spaces, which allow a good embedding in a certain sense.

Finally, chapter 7 discusses the problem of replacing a range of a complete space by another one in such a way that the completeness-property is maintained. This is motivated by {\it simplex transformations} in arrangements of pseudohyperplanes. We characterize the ranges that can be replaced and show that simplex transformations have an equivalent in complete and pseudogeometric spaces. Using a result of Ringel \cite{Ringel} we show that any two pseudogeometric spaces of VC-dimension 2 and the same boundary can be transformed into each other by using only simplex transformations, a result that does not generalize to higher dimensions.

Chapters 1 through 4 should be read in consecutive order, while chapters 5, 6 and 7 are independent from each other, but are based on the first four chapters.