Constructing Order Type Graphs using an Axiomatic Approach
share
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 <cit.> introduced exit graphs for visualizing order types in the plane. We present a new class of geometric graphs, called OT-graphs, using abstract order types and their axioms described in the well-known book by Knuth <cit.>. 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.
READ FULL TEXT