空間の有限の 2D 領域内に一連の 2D ポイントがあります (今のところ、物事を単純にするために、世界に沿った長方形としましょう)。新しい最も近い点までの距離が比較的長いセットに新しい点を挿入する非常に効率的な方法は何でしょうか?
Delaunay 三角形分割をゆっくりと構築し、検索を最大の三角形のみに制限することはできましたが、誰かが別の (より良い) アイデアを持っていることを望んでいました。
のれん、デビッド
編集:
前のすべての点を考慮して、毎回これを何千回も行う必要があることを忘れていました。ポイントセットが大きくなっても速度が遅くならないアルゴリズムを探しています。