An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings.

Let be a set of labeled points in the plane. The radial system of describes, for each , the order in which a ray that rotates around encounters the points in . This notion is related to the order type of , which describes the orientation (clockwise or counterclockwise) of every ordered triple in . Given only the order type, the radial system is uniquely determined and can easily be obtained. The converse, however, is not true. Indeed, let be the radial system of , and let be the set of all order types with radial system (we define for the case that is not a valid radial system). Aichholzer et al. ( Reconstructing Point Set Order Types from Radial Orderings, in Proc. ISAAC 2014) show that may contain up to order types. They also provide polynomial-time algorithms to compute when only is given. We describe a new algorithm for finding . The algorithm constructs the convex hulls of all possible point sets with the radial system . After that, orientation queries on point triples can be answered in constant time. A representation of this set of convex hulls can be found in queries to the radial system, using additional processing time. This is optimal. Our results also generalize to abstract order types. [ABSTRACT FROM AUTHOR]