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

Question

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

标签： algorithmgeometry

Answer 1

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