1

質問があります、

一連の点が与えられた場合、最も遠い点までの距離をできるだけ短くするという制約の下で、どのように点を配置しますか？

これは、この問題に関連しています。どうすればいいのかわかりません。誰かのポインタ？

ありがとう

4

2 に答える 2

1

ボロノイ図、おそらく最も遠い点のボロノイ図を使用する必要があります。この図では、平面が領域に分割され、同じ領域内の点が同じ最も遠い点を持ちます。

アップデート

最初に最も遠い点のボロノイ図を作成する必要があります。これはO（nlogn）時間であり、すべての頂点（円が3つの点で定義されている場合）とすべてのエッジ（円の場合）の中で最小の円の中心を見つけます。 2つのポイントで定義されます）。このアプローチの合計時間計算量はO（nlogn）です。

最小円問題のwikiページを見たところ、 O（n）時間アルゴリズムがあるようです。速度が気になる場合はチェックしてください。そうでない場合は気にしないでください。

于 2012-07-02T23:47:24.857 に答える
1

このページをチェックしてください。これを行うためのいくつかの方法について説明します。 http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

上記のリンクが機能しなくなった場合に備えて、最も簡単な方法を説明する関連部分を次に示します。

O（n2）時間アルゴリズム

  1. 与えられたセットの点が円の中にあるように、中心cに円を描きます。明らかに、この円を小さくすることができます（または、解決策があります）。
  2. サーキュラーの中心から最も遠い点Aを見つけ、同じ中心で新しい円を描き、点Aを通過することにより、円を小さくします。これらの2つの手順により、より小さな円を囲みます。新しい円が小さい理由は、この新しい円には、それを囲むのではなく、最も遠い点xを通過することを除いて、指定されたセットのすべての点がまだ含まれているためです。
  3. 円が2つ以上の点を通過する場合は、手順4に進みます。それ以外の場合は、円がセット内の別の点Bと接触するまで、中心を点Aに向かって移動して円を小さくします。

  4. この段階では、特定のセットの2つ以上のポイントを通過する円Cがあります。円に点がない円周の半分を超える円弧の間隔（点のない間隔）が含まれている場合は、円を小さくすることができます。DとEを、このポイントフリー間隔の終わりのポイントとします。DとEを円の境界に保ちながら、ケース（a）またはケース（b）のいずれかになるまで、円の直径を小さくします。

    • ケース（a）直径は距離DEです。
      • 完了です！
    • ケース（b）円Cが集合Fの別の点に接している。
      • Cの円周の半分を超える長さのポイントフリーアーク間隔が存在するかどうかを確認します。
      • そのようなポイントフリーアーク間隔が存在しない場合は、完了です。
    • そうしないと
      • 手順4に進みます。
      • この場合、3つのポイントは、長さが円周の半分未満の円弧上にある必要があります。円弧上の3つのポイントの外側の2つで手順4を繰り返します。

サンプルアプレットを含む別のページ： http ：//www.sunshine2k.de/stuff/Java/Welzl/Welzl.html

于 2012-07-03T00:29:24.013 に答える