Enumerating Order Types for Small Point Sets with Applications

摘要

Order types are a means to characterize the combinatorial properties of a finite point configuration. In particular, the crossing properties of all straight-line segments spanned by a planar n-point set are reflected by its order type. We establish a complete and reliable data base for all possible order types of size n = 10 or less. The data base includes a realizing point set for each order type in small integer grid representation. To our knowledge, no such project has been carried out before. We substantiate the usefulness of our data base by applying it to several problems in computational and combinatorial geometry. Problems concerning triangulations, simple polygonalizations, complete geometric graphs, and κ-sets are addressed. This list of applications is not meant to be exhaustive. We believe our data base to be of value to many researchers who wish to examine their conjectures on small point configurations.