StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>There are a few different ways to do this in O(n log n) time.</p> <p>One: Compute the manhattan distance <a href="http://en.wikipedia.org/wiki/Voronoi_diagram" rel="nofollow">Voronoi diagram</a> of the G points and build a point location data structure based on that. This takes O(n log n) time. For each D point, find the closest G point using the point location data structure. This takes O(log n) time per D point. Take the min of the distances between the pairs you just found and that's your answer.</p> <p>Two: You can adapt <a href="http://en.wikipedia.org/wiki/Fortune%27s_algorithm" rel="nofollow">Fortune's algorithm</a> to this problem; just keep separate binary trees for D and G points. Kind of annoying to describe.</p> <p>The next idea computes the distance of the closest pair for the infinity-norm, which is max(|x1-x2|, |y1-y2|). You can tilt your problem 45 degrees (substituting u = x-y, v = x+y) to get it into the appropriate form.</p> <p>Three (variant of two): Sort all of the points by y coordinate. Maintain d, the distance between the closest pair seen so far. We'll sweep a line from top to bottom, maintaining two binary search trees, one of G points and one of D points. When a point is d or farther above the sweep line, we remove it from its binary search tree. When a point is first encountered by the sweep line, say a D point, we (1) check the G binary search tree to see if it has any elements whose x-coordinate is within d of the new point's, updating d as necessary, and (2) insert the new point into D's binary search tree. Each point only causes a constant number of binary search tree operations plus a constant amount of additional work, so the sweep is O(n log n). The sort is too, unsurprisingly, so our overall time complexity is as desired.</p> <p>You can probably make a divide-and-conquer strategy work too based on similar ideas to three.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload