Enumerating Order Types for Small Point Sets with Applications
Enumerating Order Types for Small Point Sets with Applications
复制标题
使用应用程序枚举小点集的订单类型
作者：
O. Aichholzer;F. Aurenhammer;H. Krasser
序型是刻画有限点构形组合性质的一种手段。特别地，平面n点集所张成的所有直线段的相交性质由其序类型反映。我们为n=10或更小的所有可能的订单类型建立了一个完整可靠的数据库，该数据库包括一个小整数网格表示的每种订单类型的实现点集。据我们所知，没有这样的项目已经进行了before.We证实了我们的数据库的有用性，将其应用于计算和组合几何中的几个问题。有关三角剖分，简单的parallelizations，完整的几何图形，和k-集的问题得到解决。此应用程序列表并不意味着详尽无遗。我们相信，我们的数据库是有价值的许多研究人员谁希望检查他们的programmures上的小点配置。
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 k-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.