Point Set Reconstruction Problems

Perouz Taslakian, School of Computer Science, McGill University

We present two pointset reconstruction problems where the main goal is to embed points on the circumference of a unit circle such that the distances defined by pairs of points satisfies some given constraints. We show that when the constraint is to maximize the sum of Euclidean distances between all pairs of points, then the solution is the vertex set of a regular polygon. We also characterize such maximally even pointsets when the points are restricted to the circular grid. We then describe a polynomial-time solution to the "labeled beltway problem", where we are given the ordering of the points around the circumference of a circle and a labeling of all distances defined by pairs of points, and we want to construct a pointset such that two distances having a common endpoint have the same length if and only if they have the same label.