| Where to build a temple, and where to dig to find one (2008) | |||||||||||||
Abstract | |||||||||||||
| In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We use two different approaches to find regular polygons, depending on their number of edges. Those with o(n 0.068) edges are found by sweeping a line through the set of points, while the larger polygons are found by random sampling. We can find all the polygons with high probability in O(n 2.068+ɛ) expected time for every positive ɛ. This compares well to the O(n 2.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 | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||