Theoretical algorithm for finding a cabinet 2 points on a circle in O (n)

Question

Given n points on the contour of a unit circle, I want to calculate the next 2 points.

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

I once knew a solution for this, but forgot ... the solution includes hashing and splitting the circle into n or more fragments.

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

Answer 1

Here's the solution, which should be O (n log log n) to find the closest pair of points on the line. This is a trivial transformation from your problem - each point (x, y) on the unit circle goes to the linear coordinate x 'in the interval [0,2pi), where x' = atan2 (y, x). The idea is, once you have converted it into a one-dimensional problem, about to start hashing the x coordinates in the buckets, converting the large buckets into a smaller bucket until there is no more than one point on the bucket, then go through the list and find the closest pair . (And you will have another check to see that the points with the min and max x 'coordinates form an even closer pair than the linear minimum.)

Answer 2

Sort them by angle by placing them in bins (binsort, O(n) ); Select multiple bins in the same order as the number of points. Then go through and find the nearest pair, repeating the process in the bin if more than one point falls into it.