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). |
Remarks: |