消防署はエリアをカバーします

Question

ポイント（GPS座標）とそれらすべてのポイントを含むポリゴンが与えられれば、それらのポイントがそのエリアをどれくらいうまくカバーしているか、またはポリゴン内の任意の場所から最も近い点は？

たとえば、ニューヨークの都市境界内にすべての消防署がある場合、最悪の場合、消防車が運転する必要がある期間（緊急時）を知りたいと思います。

この問題の名前が何であるか、またはこの問題をどのように減らすことができるかについてのアイデアはありますか？それとも既存のアルゴリズムがありますか？

ありがとうございました:)

Answer 1

まずサイト（GPS座標）のセットのVoronoi diagramを構築します。ボロノイ図は、各サイトのセルが他のサイトよりもそのサイトに近いすべてのポイントからなるように、プレーンのセルへの分割を表すデータ構造です。

O(nlog(n))でFortune's sweep-line algorithmを使用して、ボロノイ図を作成することができます。ここで、nは入力サイトの数です。

次に、Voronoi細胞で繰り返します。各セルはポリゴンです。各セルについて、セルのサイトと各ポリゴンの頂点との間の距離を計算します。サイトとサイトセルの頂点との間の最長距離は、サイトに到達するために歩く必要がある最長距離です。

アルゴリズムの第2段階（各Voronoiセルの頂点を反復する）には、アルゴリズムの実行時間はO(nlog(n))であり、線形時間のみが必要です。これは、図全体の頂点の総数がサイト数とともに直線的に増加するためです。つまり、Euler's formula for planar graphsを使用してボロノイ頂点の総数を上から上に限定して表示することは、2n-5で示すことはあまり難しくありません。

フォーチュンのアルゴリズムのオープンソース実装は、Web上で見つけることができます。 This oneなどです。