Given a circle with N defined points and a point M outside the circle, find the point that is closest to M among the set of N. O(LogN)

Question

http://www.glassdoor.com/Interview/Google-Interview-RVW2382108.htm

I have tried to come with a solution to this problem. But I have not been successful.. Can any one please give me a hint as to how to proceed with this problem.

I will take 2 pair of two points each. That is, I will make 2 chords. Find out their perpendicular bisector. Using those bisectors, I will find out the center of the circle...

Moreover, I will come up with the equation of the circle. And find the point of intersection of the point M with the circle... That should be closest point. However, that point may or may not exist in the set of N points

Thanks.

Answer 1

Assuming that the points on the circumference of the circle are "in-order" (i.e. sorted by angle about the circle's center) you could use an angle-based binary search, which should achieve the O(log(n)) bounds.

1. Calculate the angle A from the point M to the center of the circle - O(1).
2. Use binary search to find the point I on the circumference with largest angle less than A - O(log(n)).
3. Since circles are convex the closest point to M is either I or I+1. Calculate distance to both and take the minimum - O(1).

Answer 2

To find a point closest to M, we need to do binary elimination of points based on planar cuts. A little pre-processing of the input points is needed after which we can find a point closest to any given point M in O(lgn) time.

1. Calculate (if not given) polar representation of points in (r,θ) format where r is the distance from center and θ is the angle from x-axis in the range (-180,180].
2. Sort all N points in increasing order of their angle from x-axis.

Note that simple binary search of a point closest to M will not work here, e.g.,

• if the given points are sorted such that θ = (-130,-100,-90,-23,-15,0,2,14,170), then for a point M with θ = -170, binary search will give -130 (40 degrees away) as the closest point whereas 170 (20 degrees away) is the closest point to M.
• if we ignore the sign while sorting (thinking that it will produce correct output), our new sorted array will look like θ = (0,2,14,15,23,90,100,130,170), binary search for a point M with θ = -6 will yield the result should be either 2 or 14 whereas 0 is the closest point to M in this case.

To perform the search operation using planar cuts,

• Find planar cut line passing through the center of circle and perpendicular to the line connecting the center of the circle with point M.
• Eliminate half of the circular plane [90+θ,-90+θ) or [-90+θ,90+θ) depending upon on in which half of the plane M lies.
• Make planar cuts parallel to the first cut and passing through the point in the middle of the previous plane and eliminate all points in the half of the plane farther from M until there are no points left in the nearer half of the plane, in which case eliminate the nearer half of the plane.
• Keep on cutting planes till we are left with one point. That point is the closest point to M. The total operation takes O(lgn) steps.

In case the data is skewed and not uniformly spread in the circle, we can optimize our planar cuts such that each cut passes through the median (based on angle) of those points which are left in the search operation.