algorithm - 一组点与特定点之间的最小距离

Question

我有一组构成路径的点的坐标(经度和纬度)，我也有一个特定的点。我想找到这个点和一组点之间的最小距离。请建议一个优化的方法，因为我必须非常频繁地进行这个查询。

Answer 1

我可能会建议使用动态凸包算法或类似的算法。在这种情况下，最远的点总是在凸包上。将您要跟踪的点添加到船体 (O(log N))，因为您知道船体上的一个点，理论上您可以在 O(log h) 中找到最远的点，但最坏的情况是 O (h) 其中 h 是凸包上的点数。在随机点集中，h 大约为 O(sqrt N)，但取决于您的点集是什么样子。