CODEWITHSUNDEEP
mathcomputational-geometry
Oren
Oren

Reputation: 2807

Theoretical Algorithm for finding closest 2 points on a circle in O(n)

Given n points on the outline of the unit circle, I want to calculate the closest 2 points.

The points are not ordered, and I need to do it in O(n) (so I cannot sort them clockwise...)

I once knew the solution for this, but forgot it... the solution includes hashing, and splitting the circle to n or more slices.

If you found an algorithm to calculate only the distance, and not the specific points, it will be good enough..

Upvotes: 4

Views: 328

Answers (2)

Jim Lewis
Jim Lewis

Reputation: 45045

Here's a solution that purports to be O(n log log n) for finding the closest pair of points on a line. This is a trivial transformation from your problem -- each point (x,y) on the unit circle maps to a linear coordinate x' in the line segment [0,2pi), where x' = atan2(y,x). The idea, once you've converted it to a 1-D problem, is roughly to start hashing the x' coordinates into buckets, repartitioning big buckets into smaller buckets until there's at most one point per bucket, then walk through the list and find the closest pair. (And you'd have one additional check to see if the points with the min and max x' coordinate form an even closer pair than the linear minimum.)

Upvotes: 2

Rex Kerr
Rex Kerr

Reputation: 167891

Sort them by angle by placing them in bins (binsort, O(n)); choose a number of bins of the same order as the number of points. Then walk through and find the closest pair, repeating the process within a bin if more than one point falls in it.

Upvotes: 0

Related Questions