Detecting all regular polygons in a point set

2009/08/17 by Greg Aloupis, Jean Cardinal, Aloupis, Greg +8
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Digital Image Processing Techniques #FOS: Computer and information sciences #cs.CG

paper · pdf · doi:10.48550/arxiv.0908.2442

11 pages, 4 figures

arxiv created 2009/08/17 · openalex publication_date 2009/08/17 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We combine two different approaches to find regular polygons, depending on their number of edges. Our result depends on the parameter alpha, which has been used to bound the maximum number of isosceles triangles that can be formed by n points. This bound has been expressed as O(n^{2+2alpha+epsilon}), and the current best value for alpha is ~0.068. Our algorithm finds polygons with O(n^alpha) edges by sweeping a line through the set of points, while larger polygons are found by random sampling. We can find all regular polygons with high probability in O(n^{2+alpha+epsilon}) expected time for every positive epsilon. This compares well to the O(n^{2+2alpha+epsilon}) deterministic algorithm of Brass.

Related

• How to Catch k Grid Points
• Efficient Enumeration of At Most k-Out Polygons
• A technique for solving the polygon inclusion problems
• Polygon Detection from a Set of Lines
• Partitions of planar point sets into polygons