Combinatorial problems on geometric graphs

Computational Geometry is a relatively young and very active field of research in the intersection of mathematics and theoretical computer science. Studying algorithms and data structures have been main objectives of this growing discipline. Although geometric graphs are structures defined by geometric properties, like x- and y- coordinates, they have a highly discrete nature. Straight lines spanned by a finite set of discrete points give rise to simple and memory efficient data structures. While not loosing the geometric information, geometric graphs additionally provide combinatorial context (like neighborhood information) that is sufficient for many applications and allows for very efficient and stable algorithms. Moreover, for many problems the geometric information is not needed for their solution. In these cases, point sets, geometric in principle, can be stored and used in a purely combinatorial way. A simple example is the construction of the convex hull of a point set, which is an intrinsic task of countless algorithms. For this it is sufficient to know for any triple a,b,c of points whether c is to the left or to the right of the straight line spanned by a and b. A data structure that stores this information is the so called order type. Not to be forced to rely on geometric information has one major advantage: It enables for simple, exact, and robust algorithms. For these reasons, Computational Geometry has become highly interweaved with fields of Discrete Geometry like Combinatorial Geometry. In the proposed project we want to explore a group of interrelated questions that can be reduced to purely combinatorial problems. One exception from this group of purely combinatorial problems is the question of blocking Delaunay triangulations on bi-colored point sets. The order type does not provide the Delaunay property for quadruples of points, an in-circle property needed for Delaunay triangulation construction. An extended order type, for instance, a "Delaunay order type" mapping the Delaunay property to purely combinatorial data, could help solving this and many other problems on Delaunay triangulations by answering how many different Delaunay triangulation exist for a given "classical" order type. But even though not of pure combinatorial nature, this subproblem is related to the other proposed problems. General methods on bi- colored point sets can be applied to the problems on compatible geometric graphs, isomorphic plane geometric graphs, questions on k-convexity, and also, of course, the Erdös-Szekeres type problems on bi-colored point sets. Further, new insights and results on any of these problems will have implications on the whole project and also to many other problems from Discrete & Computational Geometry. In the context of this project, examples for interesting classes of geometric graphs are triangulations, pseudo-triangulations, spanning trees, spanning circles, spanning paths, and (perfect) matchings. As already mentioned, the proposed problems are interrelated parts of one project. It is our strong belief that attacking these problems in a combined attempt will have synergetic effects to all parts. This will help to make considerable progress on the presented questions, to gain additional insight into their structure, and to finally answer at least some of them.

Computational Geometry is a relatively young and very active field of research in the intersection of mathematics and theoretical computer science. A main objective of this growing discipline has always been the study of algorithms and data structures, but also, with increasing importance the consideration of kombinatorial questions. Although geometric graphs are defined by geometric properties, like x- and y-coordinates, they are also of highly discrete nature. In addition to the geometric information, straight lines spanned by a finite set of discrete points provide combinatorial context, like neighborhood information or the number of certain spanned structures (for instance, empty triangles). Utilizing this combinatorial information gives rise to simple and memory efficient data structures and very time efficient and particularly stable algorithms. Furthermore, for many problems the purely geometric information is not needed for their solution. For this reasons, Computational Geometry has become highly interweaved with fields of Discrete Geometry like Combinatorial Geometry.In the concluded project we considered a group of highly interrelated questions that can be reduced to purely combinatorial problems. One very prominent example for this is the question about the number of necessary transformations, to convert one given bicolored matching into another one. A bicolored matching is a geometric graph on a bicolored point set, where each point is incident to exactly one straight line, each straight line matches two equally colored points, and no edges cross. A transformation converts a matching into another one, while ensuring that the union of the edges of both matchings spanned on the common point set is still crossing free (except for identical edges). In the cause of this project, we were able to improve the known exponential bound on the number of necessary transformations to a (asymptotically perfect) linear bound and thereby giving a concluding answer to this problem. In addition, we provide an efficient Algorithm for finding such an optimal sequence of transformations.Among many other results the work in this project resulted in a major step in the class of the so called Erdös-Szekeres type problems, a special subgroup of Ramsey-theorie. We improved the bounds on the number of empty convex triangles, quadrangles, and pentagons that are guaranteed to be spanned by any finite point set in the plane. Further, we investigated and improved these bounds for the cases, where the mentioned polygons are not necessarily convex and/or need not to be empty. Moreover, we also improve the bound on the number of empty triangles on general graphs, where edges need not be straight lines. In a seminal work we published the first non-trivial lower bounds for the number of empty simplices (triangles in the plane, tetrahedrons in 3D, etc.) spanned by multicolored, multidimensional finite point sets. As a side effect of this work, we also provide various results on triangulations of mulitdimensional point sets, including an improved bound on the number of simplices in high dimensional triangulations.The work conducted in this project effected many different research topics, not restricted to the topics specified in the application phase. This is natural to projects in fundamental research, as synergies and side effects cannot always be predicted and are a very welcomed surprise. In total, this project resulted, so far, in 36 publications in scientific journals and at refereed conferences and many initiated topics are still under consideration and subject to ongoing research.