Enumerating Order Types for Small Point Sets with Applications
O. Aichholzer, F. Aurenhammer, and H. Krasser
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
-point set are reflected by its
order type. We establish a complete and reliable data base for all possible
order types of size
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
addressed. This list of possible 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.
Reference: O. Aichholzer, F. Aurenhammer, and H. Krasser.
Enumerating order types for small point sets with applications.
Order, 19:265-281, 2002.