Order type invariant labeling and comparison of point sets
Greg Aloupis, Muriel Dulieu, John Iacono, Stefan Langerman, Suneeta Ramaswami, Stefanie Wuhrer · 2012
We consider the problem of computing an order type in-variant labeling for a given set of n points. In 2D, such a labeling can be constructed in O(hn2) time, where h is the size of the smallest convex layer. In 3D the time complex-ity is O(n3 log n) if the point set is in general position1. This is useful to test if two point sets have the same order type within the same time bounds. It can also be used as preprocessing for any order type invariant algo-rithm, such as triangulation/tetrahedralization, or polygo-nization. 1