追蹤一組點中最大距離的最佳方法？

Question

假設我有一個2維點的集合，以及一種確定它們之間距離的方法。這個集合經常被修改，添加了額外的點並刪除了現有的點。在任何時候，我都需要知道點之間的最大和最小距離，即最遠的兩點之間的距離以及兩點之間最近的距離。有沒有一種數據結構或算法可以很好地完成這項任務？每次點改變時，我寧願不必重新計算整個距離。

Answer 1

從理論上講，您可以通過存儲您所擁有的點的convex hull高效地完成此操作。

每當您添加一個新點時，請測試以確定它是否位於此polytope的內部。如果是這樣，則保留最大距離。如果不是，那麼它可能已經改變。

同樣，如果您從內部刪除一個點，最大距離（直徑）被保留，所以不做任何改變。但是，如果刪除邊界點，則必須重新計算凸包。

如果您在2維中，那麼當您添加或從邊界移除時，多邊形的至多兩側都會受到影響。這些應該很容易計算，具體取決於你如何存儲信息（例如一系列線段）。

編碼這可能有點痛苦，但最簡單的方法是標記邊界上的點，然後有一個函數，測試點是否位於標記點的凸包內。

Answer 2

我一點也不確定這是最好的，但這是我現在能想到的最好的。

將最大值與在該距離處的一組點對一起保存。 （最大值不一定是唯一的。）

同樣當然最小。

• 當您添加一個點，計算所有其他點新點的距離，而其對應的一組端點對替換您保存的最大值和最小值在一起，如果新的點在一個更好的最大或最小參與，或者如果它匹配當前最好的，則更新該組端點。

• 刪除點時，檢查是否清除整個記住的最小或最大點集。如果沒有，你不需要做任何事情。但如果是這樣，我認爲你需要重新計算一切。

爲了最大化計算，我相信PengOne的建議可以告訴你，如果你可以完全跳過計算。

Answer 3

而不是使用凸包（如在另一個答案中建議），你可以使用Delaunay三角？

最小投影距離：

要計算從節點的最短距離的任何其他集合中，你應該只需要檢查節點的近鄰，即那些通過在邊緣連接到它三角測量。

因此，如果插入新節點，更新三角測量，找到新節點的鄰居以及更新中「涉及」的任何其他節點，計算此本地「更新」集中所有節點的距離，並且檢查是否找到新的最小值。類似地，如果現有節點被刪除，則再次更新三角測量並重新計算「涉及」的所有節點的距離。

有一類所謂的「增量」算法，可以用來構建Delaunay三角剖分，只需要在插入/刪除新節點時對整個三角剖分進行局部修改，所以這就是我想要的方法類型建議頻繁插入/刪除。

最大距離：

如凸包風格回答表明，你只需要重新計算邊界節點之間的距離，如果一個新的節點是在現有的三角測量之外，或如果現有的邊界節點加入已被刪除。

希望這會有所幫助。 「