Detecting all regular polygons in a point set

Details Detecting all regular polygons in a point set Detecting all regular polygons in a point set

2009-08-17

arxiv.org/abs/0908.2442v1

Computer Science

Computational Geometry

11 pages, 4 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Detecting all regular polygons in a point set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Detecting all regular polygons in a point set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting all regular polygons in a point set will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-7972