algorithm - 找到集合中每个点的最近点

Question

我有一组 n 形式的点(X,Y)，我想找到最接近集合中每个点的点，另一个点也属于同一个集合。

朴素的算法很简单，O(n^2)但我想做更好的事情。

任何帮助表示赞赏。

Answer 1

您只需要 O(N) 时间即可使用Delaunay triangulation获得最接近每个点的点。只需从每个点开始选择一条长度最短的边。

并且可以在 O(N log N) 时间内找到 Delaunay 三角剖分。