论文标题
使用公理方法构建订单类型图
Constructing Order Type Graphs using an Axiomatic Approach
论文作者
论文摘要
平面中的给定订单类型可以用点集表示。但是，可能很难识别某些点三元的方向。最近，Aichholzer \ etal \ cite {abh19}引入了出口图，以可视化平面中的顺序类型。我们使用抽象顺序类型及其公理，在Knuth \ cite \ cite {k92}中介绍的抽象顺序类型及其公理。每个ot-graph对应于唯一的订单类型。我们开发了有效的算法，用于识别ot图和计算平面中给定的订单类型的最小ot图。我们为平面中多达9点的所有阶类型提供实验结果，包括对出口图和OT图形的比较分析。
A given order type in the plane can be represented by a point set. However, it might be difficult to recognize the orientations of some point triples. Recently, Aichholzer \etal \cite{abh19} introduced exit graphs for visualizing order types in the plane. We present a new class of geometric graphs, called {\em OT-graphs}, using abstract order types and their axioms described in the well-known book by Knuth \cite{k92}. Each OT-graph corresponds to a unique order type. We develop efficient algorithms for recognizing OT-graphs and computing a minimal OT-graph for a given order type in the plane. We provide experimental results on all order types of up to nine points in the plane including a comparative analysis of exit graphs and OT-graphs.
