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

Oswin Aichholzer, Vincent Kusters, Wolfgang Mulzer +2

Let $P$ be a set of $n$ labeled points in the plane. The radial system of $P$ describes, for each $p\in P$, the order in which a ray that rotates around $p$ encounters the points i…