Where to build a temple, and where to dig to find one
Greg Aloupis, Jean Cardinal, Sébastien Collette, John Iacono, Stefan Langerman · 2006
In this paper, we analyze the time complexity of find-ing regular polygons in a set of n points. We use two different approaches to find regular polygons, depend-ing on their number of edges. Those with o(n0.068) edges are found by sweeping a line through the set of points, while the larger polygons are found by ran-dom sampling. We can find all the polygons with high probability in O(n2.068+) expected time for ev-ery positive . This compares well to the O(n2.136+) deterministic algorithm of Brass [1]. Our method can also be used to find incomplete regular polygons, where up to a constant fraction of the vertices are missing. 1