The nearest pair of points along the line

Question

I have two sets of two-dimensional points, separated from each other by a line in the plane. I would like to effectively find a pair of points, consisting of one point from each set, with a minimum distance between them. There is really convenient paper Radu Lity, The closest pair for two divided sets of glasses, but instead of the Euclidean distance, the distance metric L1 (Manhattan) is used.

Does anyone know of a similar algorithm that works with Euclidean distance?

I can just see the extension of the standard division and finish the closest pairing algorithm - divide the two sets into a midline perpendicular to the original splitting line, recurs from two sides, and then look for a closer pair consisting of one point on each side of the median. If the minimum distance from the recursive step is d, then the companion for a point on one side of the median must lie inside a box with dimensions 2d * d. But unlike the original algorithm, I see no way to relate the number of points in this field, so the whole algorithm just becomes O (m * n).

Any ideas?

Answer 1

Eugene’s answer works, but it requires a lot of effort without the support of the library: calculate the full Voronoi diagram and the additional scan line algorithm. It is easier to list for both sets of points the points that Voronoi cells intersect the dividing line in order, and then check all pairs of points whose cells intersect using the linear time merge step.

To calculate the necessary fragment of the Voronoi diagram, suppose that the x axis is a dividing line. Sort the points in the set using the x-coordinate, discarding points with a larger y than any other point with an equal x. Start scanning the points in the x-coordinate order by clicking them on the stack. Between clicks, if the stack has at least three points, say p, q, r, when r was pressed most recently, check if the bisecting pq line intersects the dividing line after the bisecting qr line. If so, drop q and repeat the test with the new triple. Crude ASCII art:

Case 1: retain q ------1-2-------------- separating line / | p / | \ | q-------r Case 2: discard q --2---1---------------- separating line \ / p X r \ / q 

Answer 2

For each point in one set, find the nearest point in another set. At the same time, save only one pair of points with a minimum distance between them. This reduces the given task to another: “An algorithm for all points in the set A of the nearest neighbor in the set B” , which can be solved using the line sweep algorithm over (1) one set of points and (2) the Voronoi diagram for another set.

The complexity of the algorithm is O ((M + N) log M). And this algorithm does not use the fact that two sets of points are separated by a line.

Answer 3

A typical approach to this problem is the sweep algorithm. Suppose you have a coordinate system that contains all the points and a line separating points from different sets. Now imagine a line perpendicular to the separation line, jumping from point to point in ascending order. For convenience, you can rotate and translate the set of points and the dividing line so that the dividing line is equal to the x axis. The scan line is now parallel to the y axis.

Moving from point to point using a sweep line, tracking the shortest distance of two points from different sets. If the first few points are from the same set, it is easy to find a formula that tells you which one you need to remember until you press the first point from another set.

Suppose you have a total of N points. You will need to sort all the points in O (N * log (N)). The sweep algorithm itself will work in O (N).

Answer 4

Well, what about this:

• determine which side is any point:

  • let P be your points (P0, ... Pi, ... Pn)
  • let A, B be the endpoints of the separator line
  • so: side (Pi) = signum of ((BA). (Pi-A))
  • this is based on the simple fact that the signum of scalar vector multiplication (the point product) depends on the order of the points (see the triangle / polygon winding rule for more information)

• we find the minimum distance of any (Pi, Pj), where side (Pi)! = side (pj)

  • therefore, we first calculate all sides for all points O (N)
  • then the cycle through all Pi and inside that for
  • loop through all Pj and search for the minimum distance.
  • if the groups Pi and Pj aprox. equal tahn size is O ((N / 2) ^ 2)

• you can further optimize the search by "sorting" the points Pi, Pj by the "distance" from AB

  • you can use another point product for this, instead (BA)
  • use a perpendicular vector for it, say (CA)
  • discard all points from Pi2 (and similar Pj2 also)
  • where ((BA). (P (i1) -A)) is close to ((BA). (P (i2) -A))
  • and | ((CA). (P (i1) -A)) | & L; <| ((CA) (P (i2) -A).) |
  • beacuese, which means that Pi2 is located behind Pi1 (much further from AB)
  • and close to the normal AB, approaching Pi1
  • the complexity after this optimization is highly dependent on the data set.
  • should be O (N + (Ni * Nj)), where Ni / Nj is the number of remaining points Pi / Pj
  • you need 2N point products, Ni * Nj distance comparison (no need to do sqrt-ed)

Answer 5

(I'm not sure that this has any resemblance to David's idea ... I just saw it now after I logged in to post my thoughts.) For the sake of argument, let’s say we wrap everything so that the dividing line - x axis and sorted our points by x coordinate. Assuming that N is not too large if we scan along the x axis (i.e., intersect our sorted list a and b), we can save a record of the total minimum and two lists of traversed points. The current scan point is checked for each transferred point from another list, while the distance from the point in the list to (the x-coordinate of our scan, 0) is greater than or equal to the total min. In the example below, when you reach b2 , we can stop testing at a2 .

  scan -> Y | a2 | | a1 a3 X-------------------------- | b1 b3 | b2