Order Types and Extremal Combinatorial Geometry

We propose a research project in the field of computational geometry, a sub-field of mathematics and theoretical computer science that focuses on the theoretical backgrounds of how computer programs can process geometric entities. Our research has applications in extremal combinatorial geometry, where we are interested in estimating the numbers of different networks defined by straight-line connections drawn between sites (represented by points) on a flat surface, similar to straight routes connecting cities on a map. Such drawings are called geometric graphs. Geometric graphs can be classified in various ways, for example whether or not they contain crossings or cycles. For many classes without crossings, it is known that the number of different geometric graphs (obtained by connecting given points) is minimized when the points are placed on a circle. Analogously, arranging the points in that way maximizes the number of such graphs for many geometric graph classes with crossings. One objective of our work is to characterize point sets that maximize or minimize the number of geometric graphs for certain classes. For such problems, we are usually not interested in the exact position of the points, but how they are placed relative to each other, since, in general, our problem does not change if we slightly move a few points. The order type of a point set tells us in which order we encounter three points of the set when walking along the boundary of the triangle defined by these points in counterclockwise direction; that is, we get the orientation of each triple of points. In previous work, we defined a relation on order types by comparing the set of crossing-free geometric graphs each order type admits. We characterized order types among which there are point sets that have the most or the least number of certain classes of geometric graphs. However, this characterization is rather general. We plan to obtain relations between order types that provide more insight into the structure of maximizing and minimizing point sets. In particular, we are interested in bounding the number of triangulations (geometric graphs in which each bounded area is a triangle). We will attempt to prove a long- standing conjecture stating that the number of triangulations is minimized by a certain order type, using the insights obtained from different relations and local transformations (for example changing the orientation of a single point triple). Apart from bounding the number of geometric graphs, we are interested in relations between different order types in its own right. We will analyze different types of local operations that allow transforming one order type into another.

The project is in the field of computational and combinatorial geometry, which can be seen in-between discrete mathematics and theoretical computer science. Computational geometry has applications in, e.g., computer graphics and geographic information systems, from which triangular meshes are well-known. Such triangulations are examples of plane geometric graphs, in which points are connected by segments that do not cross. Even the simple case in which all points are in the plane provides us with many research problems. For a bunch of points, there is in general a large number of different plane geometric graphs that can be drawn on them. It is thus natural to ask what is the smallest or largest number of graphs (e.g., triangulations) that we can obtain. While there are infinitely many ways to place a fixed number of points, one can observe that, in general a small change in the point's position does not change the number of triangulations. Thus, researchers devised ways of classifying point sets into a finite set of classes that behave in the same way. One such classification is the one of order types, that basically captures the orientation of any three points in the point set. Insights on order types are thus heavily connected to the fundamental question on the number of geometric graphs. We considered problems related to order types and the number of geometric graphs, e.g., how order types are related to each other. For example, there are pairs of different order types such that we can draw all plane geometric graphs of one also on the other. One question of the project was how changing the order type (e.g., moving a single point) affects the number of plane geometric graphs that can be drawn on that point set. We considered the simple case of a single point moving inside a circle containing the other points. Even this simple case has a rich combinatorial structure, which we examined. The methods used lead to the development of a faster algorithm for computing the so-called simplicial depth of a high-dimensional data point, a measure how central the point is. Another result is the actual improvement of the lower bound on the maximum number of plane geometric graphs. We described point configurations on which more such graphs can be drawn than on any other currently known configuration. We obtained results in more specialized lines of research. Our topics can be considered fundamental research. As such, they lack straight-forward applications. Nevertheless, we consider our results a contribution to deepen understanding of such fundamental mathematical structures. This is supported by the fact that several results obtained during the funding period lead to publications in journals with good reputations.