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

Question

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..

Answer 1

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.

Answer 2

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.)