algorithm - 如何找到二维点集的最近对距离？

Question

我遇到了以下问题，我无法找到一种方法来使用分而治之找到最近的配对距离，有人可以帮忙吗？

L 是 x 坐标为负的所有点之间的最近对距离，R 是 x 坐标为正的所有点之间的最近对距离。

假设至少有 2 个正点和 2 个负 x 坐标点。如果 L<R 并且在区间 (-L/2, R/2) 中没有任何点具有 x 坐标，那么最近对距离是多少？

Answer 1

区间内没有点有 x 坐标 (-L/2, R/2)

x <= -L/2因此，左边的点 ( ) 和右边的点( )之间的最近距离x >= R/2是如果这两个点在边界上（具有相同的y坐标）：距离 =L/2 + R/2

L < R

所以，(L/2 + R/2) > (L/2 + L/2) = L

换句话说，左边一点和右边一点之间的最短距离总是大于L，L最短距离也是如此。