私は2次元の点の集合とそれらの間の距離を決定する方法を持っていると仮定します。このコレクションは頻繁に変更され、追加ポイントが追加され、既存ポイントが削除されます。どの時点でも、ポイント間の最大距離と最小距離、つまり最も離れた2点間の距離と、最も近い2点間の距離を知る必要があります。このタスクに特に適したデータ構造やアルゴリズムはありますか？私はポイントが変わるたびに、距離の集合全体を再計算する必要がない方がよいでしょう。ポイントのセットで最大距離をトラッキングする最も良い方法は？
理論的には、あなたが持っているポイントのconvex hullを保存することで、これを効率的に行うことができます。
新しいポイントを追加するときはいつでも、それがこのpolytopeの内部にあるかどうかをテストします。そうであれば、最大距離は保存されます。そうでない場合は、変更されている可能性があります。
同様に、内部からポイントを削除すると、最大距離（直径）は保持されるため、何も変更しません。ただし、境界点を削除する場合は、凸包を再計算する必要があります。
2次元の場合、境界線を追加または削除すると、ポリゴンの最大2辺が影響を受けます。これらの情報は、情報の格納方法（たとえば、一連の線分など）に応じて、計算が容易でなければなりません。
これをコード化するのは少し難しいかもしれませんが、最も簡単な方法は境界上の点をマークし、点がマーク付き点の凸包の内側にあるかどうかをテストする機能です。
私はこれが一番良いとは確信していませんが、今は私が考えることができる最高のものです。
maxを、その距離のポイントのペアのセットとともに保存します。 （最大値は必ずしも一意ではありません）
もちろん最小値と同じです。
あなたは、ポイントを追加する他のすべてのポイントに新しい点の距離を計算し、新たな点が優れて最大または最小に参加した場合、エンドポイントのペアの対応するセットと一緒に保存した最大と最小を置き換え、現在のベストと一致する場合はエンドポイントのセットを更新します。
ポイントを削除するとき、ポイントが記憶された最小または最大ポイントセット全体を消去するかどうかを確認します。そうでない場合は、何もする必要はありません。しかし、それがあれば、私はあなたがすべてを再計算する必要があると思います。
計算を最大限にするために、PengOneの提案は計算を完全にスキップできるかどうかを教えてくれると思います。
（別の回答で示唆されているように）凸包を使用するのではなく、Delaunay三角測量を使用できますか？あなたが唯一のノードのすぐ隣をチェックする必要があるのセット内のノードから他への最短距離を計算するのに
、エッジによってそれに接続されているもの、すなわち：
分の距離に三角測量
したがって、新しいノードが挿入された場合、三角測量を更新し、新しいノードの近隣ノードと更新に「関わった」ノードを見つけ、このローカルの「更新」セット内のすべてのノードの距離を計算し、新しい最小値が見つかったかどうかを確認してください。同様に、既存のノードが削除された場合は、再度三角測量を更新し、「関連する」すべてのノードの距離を再計算します。
新しいノードの挿入/削除時に全体的な三角形分割のローカル修正を必要とするDelaunay三角形分割を構築するために使用できる、いわゆる「インクリメンタル」アルゴリズムがあります。頻繁な挿入/削除を推奨します。
最大距離：
凸包スタイルの回答で示唆したように、新しいノードを既存の境界ノードの既存の三角測量の外かあれば追加された場合、あなただけの境界ノード間の距離を再計算する必要があります削除されました。
これが役に立ちます。
"新しいポイントを追加するたびに、そのポイントがこのポリトープの内部にあるかどうかを確認するためにテストしてください。そうであれば、最大距離は保持されます。 これは本当ですか？簡単な例として、2Dで円の中に12個の点が配置されているとします。中心に新しいポイントを追加すると、最大距離が増加します。 –
@ケビン（Kevin）：1組の点が与えられると、それらのうちの2つの間の最大距離は点の凸包の直径です。私の主張はこの事実に従います。 – PengOne
あなたは正しいと思います。おっと、ありがとう。 –