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 acenter 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: |

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