最接近的点对 平面情况
我正在查看维基百科条目以了解如何解决此问题。它列出了五个步骤
1.沿 x 坐标对点进行排序
2.通过垂直线 x = xmid 将点集分成两个大小相等的子集
3.在左右子集中递归地解决问题。这将分别给出左侧和右侧最小距离 dLmin 和 dRmin。
4. 求一对点之间的最小距离 dLRmin，其中一个点位于分割垂线的左侧，第二个点位于分割垂线的右侧。
5.最终答案为dLmin、dRmin、dLRmin中的最小值。
第四步我有点难以理解。如何选择线左侧的点与线右侧的点进行比较。我知道我不应该比较所有点，但我不清楚如何选择要比较的点。请不要给我发送链接，我已经搜索过，访问过很多链接，但没有找到可以帮助我理解步骤 4 的解释。
谢谢
Aaron
I am looking at the wikipedia entry for how to solve this. It lists five steps
1.Sort points along the x-coordinate
2.Split the set of points into two equal-sized subsets by a vertical line x = xmid
3.Solve the problem recursively in the left and right subsets. This will give the left-side and right-side minimal distances dLmin and dRmin respectively.
4.Find the minimal distance dLRmin among the pair of points in which one point lies on the left of the dividing vertical and the second point lies to the right.
5.The final answer is the minimum among dLmin, dRmin, and dLRmin.
The fourth step I am having trouble understanding. How do I choose what point to the left of the line to compare to a point right of the line. I know I am not supposed to compare all points, but I am unclear about how to choose points to compare. Please do not send me a link, I have searched, gone to numerous links, and have not found an explanation that helps me understand step 4.
Thanks
Aaron
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您的问题的答案在维基百科文章的下一段中：
我认为我无法比他们已经说得更清楚了，但是您对算法的这一步有任何具体问题吗？
The answer to your question was in the next paragraph of the wikipedia article:
I don't think I can put it much clearer than they already have, but do you have any specific questions about this step of the algorithm?