Points and Combinatorics
by
Oswin Aichholzer
TU Graz, IST

A finite point set in the Euclidean plane is the underlying structure for many problems in discrete geometry. For several questions only their combinatorial properties have to be considered and so-called order types are a common tool to provide these combinatorial structure.

In this talk we report on a complete and reliable data base of all realizable order types in the plane (that is, planar point sets) of cardinality up to 11. Moreover we present a novel and efficient method for a complete extension to order types of larger cardinality in an abstract sense, that is, without the need to store or realize the sets.

Based on these results in the second part we present applications of this data base to various problems from discrete geometry. Questions concerning intersection properties, convexity, triangulations, polygonization, and others are addressed. This includes classic problems like searching for (empty) convex k-gons (happy end problem), decomposing sets into convex regions, counting structures like triangulations or pseudo-triangulations. As an outstanding result we have been able to determine the exact rectilinear crossing number for up to n=17 and slightly improved their asymptotic upper bound.

Date received: March 20, 2005