Efficient Algorithms for Detecting Regular Point Configurations
Authors: Luzi Anderegg, Mark Cieliebak, and Giuseppe Prencipe
Reference: In "Proceedings of the 9th Italian Conference on Theoretical Computer Science (ICTCS 2005)". Certosa di Pontignano (Siena), Italy, October 2005. To appear.
Download: PS (.ps) or PDF (.pdf)
Abstract: Abstract. A set of n points in the plane is in equiangular configuration if there exist a center and an ordering of the points such that the angle of each two adjacent points w.r.t. the center is 360/n, i.e., if all angles between adjacent points are equal. We show that there is at most one center of equiangularity, and we give a linear time algorithm that decides whether a given point set is in equiangular configuration, and if so, the algorithm outputs the center. A generalization of equiangularity is \sigma- angularity, where we are given a string \sigma of n angles and we ask for a
center such that the sequence of angles between adjacent points is \sigma. We
show that \sigma-angular configurations can be detected in time O(n^4 log n).

Note: electronic versions may not always correspond exactly to printed versions.