Order types of point sets in the plane are mappings that assigns to each ordered triple of points an orientation, that is, clockwise, counter-clockwise, or collinear. Enumerating order types for small point sets, we established a complete and reliable data base of inequivalent point sets in general position (no collinear points) of cardinality up to 11. Exploiting this point set order type data base, a collection of applications and results on several tasks in computational and combinatorial geometry was obtained.
Figure: There are three inequivalent 5-point order types in the plane.
A triangulation of a point set S in a plane is a maximal straight-line graph with nodes S, or equivalently, a partition of the convex hull of S into triangles such that the vertices of the triangles are exactly S. We achieved some results towards compatible triangulations, still leaving open the main conjectures on this topic. Playing with triangulations we obtained a collection of geometric games on triangulations. With respect to pseudo-triangulations, we were able to construct nasty point sets allowing triangulations without pointed spanning trees.
Figure: Compatible triangulations for point sets S1 and S2.
A pseudo-triangle is a simple polygon with exactly three small interior angles, i.e., less then pi. A pseudo-triangulation on a point set S is a partition of the convex hull of S into pseudo-triangles such that the union of vertices of the pseudo-triangles is exactly S. As the search for the extremal numbers of triangulations is still ongoing, our surprising result is that convexity minimizes pseudo-triangulations, that is, point sets in convex position minimize the number of different pseudo-triangulations among sets of equal cardinality. In contrast to standard flips in triangulations, adapting (pseudo)-triangulations with a near-linear number of edge flips is possible with an additional flip type. This flip type also has an interpretation in a spatial embedding of pseudo-triangulations in three-space. Exploiting this concept, we also obtained a generalization of pseudo-triangulations to higher dimensional pseudo-simplicial complexes from maximal locally convex functions.
Figure: A pseudo-triangulation on a set of 9 points.
The rectilinear crossing number of a graph G is the minimum number of crossings attained by a straight-line drawing of G in the plane. On the crossing number of complete graphs we were able to calculate the exact values for rectilinear drawings on up to 12 points. To achieve results on point sets beyond size 12, we developed the technique of abstract order type extension and new results on the rectilinear crossing number provided the exact values for up to 17 points. Moreover, we established an improved asymptotic upper bound on the rectilinear crossing constant.
Figure: An optimal rectilinear drawing of K12 attaining 153 crossings.