讓 A 和 B 是兩組點，每組由 n 個點組成，都位于單位正方形 S 中。我試圖找到一種有效的演算法來找到最大的磁盤 D，使得：
(i) D 的中心在 S。
(ii) D 的內部是空的。
(iii) D 的邊界至少與 A 的一個點和 B 的一個點相接觸。
我對這個問題有一個真正的問題。任何提示都會很有用。
uj5u.com熱心網友回復：
為了完成 Yves Daoust 的部分解，計算以 S 為界的 Voronoi 圖（與 Delaunay 三角剖分對偶）。我們可以在某個 Voronoi 頂點（即 S 內部的一個點，其中最近的三個點在 A ∪ B 中是等距的，或者是 S 邊界上的一個點，其中 A ∪ B 中最近的兩個點是等距的）其中一個最近的點在 A 中，另一個在 B 中。
這樣一個頂點作為中心顯然是可行的。如果我們嘗試取任何其他中心，那么我們可以應用斯塔克的觀察。這個中心必須與 A 中的一個點和 B 中的一個點等距，所以假設 A ∩ B 是空的（我真的不想考慮退化的情況；我們總是可以擾亂我們的出路），我們可以滑動沿 AB 的垂直平分線的中心，直到我們到達第三個點或邊界。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422796.html
標籤：
上一篇：字串中的子字串搜索（Java）