の形式の n ポイントのセットがあり、セット(X,Y)内の各ポイントに最も近いポイントを見つけ、他のポイントも同じセットに属します。
素朴なアルゴリズムは単純O(n^2)ですが、もっと良いことをしたいと思っています。
どんな助けでも大歓迎です。
質問する
987 次
1 に答える
7
Delaunay triangulationを使用して、各ポイントに最も近いポイントを取得するのに必要な時間は O(N) だけです。各点から始めて、長さが最小のエッジを選択するだけです。
また、ドローネ三角形分割は O(N log N) 時間で見つかります。
于 2012-09-20T17:15:53.940 に答える