覆蓋區域的消防部門

Question

給定一組點（GPS座標）和包含所有這些點的多邊形，可以確定這些點覆蓋區域的多麼好，或者多邊形內任何位置到該區域的最長距離最近的點是？例如，如果我擁有紐約市境內的所有消防部門，我想知道在最壞的情況下消防車必須駕駛多久（以防緊急情況發生）。

關於這個問題的名稱是什麼或者這個問題可以減少到什麼的任何想法？或者是否有任何現有的算法？

謝謝:)

Answer 1

首先構建了一套網站的Voronoi diagram（GPS座標）。 Voronoi圖是一種數據結構，表示將平面劃分爲單元格，每個單元格爲一個單元格，這樣每個單元格的單元格就包含了與該網站相比其他任何網站更接近的所有點。

構建Voronoi圖可以在O(nlog(n))使用Fortune's sweep-line algorithm完成，其中n是輸入網站的數量。

然後迭代Voronoi單元。每個單元格都是一個多邊形。對於每個單元格計算單元格的站點與每個多邊形頂點之間的距離。站點與站點單元頂點之間的最長距離是人們爲了到達站點而必須走的最長距離。

該算法的運行時間爲O(nlog(n))作爲該算法的第二階段（遍歷每個Voronoi單元的頂點）只需要線性時間。這是因爲整個圖中頂點的總數隨着站點的數量而線性增長。也就是說，使用Euler's formula for planar graphs來顯示Voronoi頂點的總數與2n-5之間的界限是不太難的。

您可以在網上找到一些Fortune算法的開源實現。例如This one。