Realizing Site Permutations.
Stéphane Durocher, Saeed Mehrabi, Debajyoti Mondal, Matthew Skala · 2011
Given n fixed sites on the plane, there are several ways to determine a permutation of the sites as a function of a unit vector u or a vantage point v. Given such a scheme and a permutation π, we can ask whether there is any unit vector or vantage point for which the permutation is π. We give linear-time algorithms for this realization problem under three schemes for determining permutations: sweeping a line across the sites in a direction u; expanding a circle starting from a vantage point v; and sweeping a ray from v to give a cyclic permutation.