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

TL;DRAbstract

Let [Formula: see text] be a set of [Formula: see text] labeled points in the plane. The radial system of [Formula: see text] describes, for each [Formula: see text], the order in which a ray that rotates around [Formula: see text] encounters the points in [Formula: see text]. This notion is related to the order type of [Formula: see text], which describes the orientation (clockwise or counterclockwise) of every ordered triple in [Formula: see text]. Given only the order type, the radial system is uniquely determined and can easily be obtained. The converse, however, is not true. Indeed, let [Formula: see text] be the radial system of [Formula: see text], and let [Formula: see text] be the set of all order types with radial system [Formula: see text] (we define [Formula: see text] for the case that [Formula: see text] is not a valid radial system). Aichholzer et al. (Reconstructing Point Set Order Types from Radial Orderings, in Proc. ISAAC 2014) show that [Formula: see text] may conta

Chat with Paper

AI Agents for this Paper