寻找集合中每个点的最近点

Question

4

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

朴素算法简单且O(n^2)，但我想做得更好。

感谢您的任何帮助。

- Aman Deep Gautam

我之前知道这个，但是我不明白它是如何工作的。你能否给一些解释或者一些链接来解释这个算法？ - Aman Deep Gautam

此外，我想要每个点的最近点，因此我必须修改该算法。 - Aman Deep Gautam

我的错，没有仔细阅读。至于你的问题，我认为没有更好的方法。 - nhahtdh

@nhahtdh，我不明白这个问题为什么会被认为是重复的。那个问题的作者本身已经承认他在问题中使用的方法是完全错误的，并且他想要做一些不同的事情。此外，那个问题中没有任何一个答案与这个问题的答案相匹配。我觉得它们完全不同。我不明白为什么它们被认为是重复的。 - Aman Deep Gautam

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Evgeny Kluev · Accepted Answer

使用Delaunay三角剖分，您只需要O(N)的时间即可获得每个点的最近点。只需从每个点开始选择长度最小的边即可。

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