Order Types of Point Sets in the Plane

H. Krasser

Abstract:

Order types are a means to characterize the combinatorial properties of a finite point set in the plane. In particular, the crossing properties of all straight-line segments spanned by a point configuration are reflected by its order type. We establish a complete and reliable data base for all different order types of size up to $11$. To the best of our knowledge, such a project has not been carried out before, not even for point sets of smaller size. We discuss several applications of this data base and related techniques to prominent problems in computational and combinatorial geometry. These include problems on crossing-free graphs like triangulations or simple polygonalizations, but also general crossing problems like the rectilinear crossing number.



Reference: H. Krasser. Order Types of Point Sets in the Plane. PhD thesis, Institute for Theoretical Computer Science, Graz University of Technology, Austria, October 2003.