### otero1991's blog

By otero1991, 12 years ago,

I wonder if somebody can help me to solve this problem: There is a set X of N point on the plane not two sharing the same x-coordinate, and a set Y of S points. The task is to compute for each point on X the distance to its closest point on Y with a precision of 10^-2 N,S<=10^5 and the coordinates of the points x,y <=10^6

UPD: Sorry for my English I corrected a mistake in the first line

• +3

| Write comment?
 » 12 years ago, # |   0 http://en.wikipedia.org/wiki/Delaunay_triangulation NLogN with any precision
 » 12 years ago, # | ← Rev. 2 →   +8 You can use the following heuristics: choose a random line and project all points on it. Then, for each point X, move two pointers in the both directions and stop a one when |posX - posY| >  = Ans, where the expression under modulo is distance between projections of X and some current point Y and Ans is the best answer for the X at this moment.This algo is easy to implement and it works good in average, but fails on a special test cases (something like 'a lot of points on a circle'). I've heard that it works in in the 'find two nearest points' problem.You can also take a look at the Codechef's CLOSEST problem and its editorial.
•  » » 12 years ago, # ^ | ← Rev. 2 →   +8 but fails on a special test cases (something like ‘a lot of points on a circle’) The test is: X = points on the large circle (coordinates are rounded to integers), Y = points near the center of the circle it works in O(NsqrtN) in the ‘find two nearest points’ problem. It's true even for more complicated problem, in case X = Y (for each point from X find the nearest one from Y).