16

平面上の n 点を指定します。いいえ 3 は同一線上にあります。

数 k が与えられます。

k ポイントの凸包が、k ポイントのサブセットの任意の凸包の中で最小の周囲長を持つように、k ポイントのサブセットを見つけます。

O(n^kk log k) で実行される単純なメソッドを考えることができます。(サイズ k のすべてのサブセットの凸包を見つけ、最小値を出力します)。

これはNPの問題だと思いますが、還元に適したものが見つかりません。

誰でもこの問題についてアイデアを持っていますか?

例、

the set of n=4 points {(0,0), (0,1), (1,0), (2,2)} and k=3

結果：

{(0,0),(0,1),(1,0)}

このセットには 3 つのポイントが含まれているため、結果の凸包と周囲は、他の 3 つのポイントのセットよりも小さくなります。

4

4 に答える 4

9

これは、O(kn^3) 時間と O(kn^2) 空間 (または、実際のポイントが必要な場合は O(kn^3)) で実行できます。

この論文: http://www.win.tue.nl/~gwoegi/papers/area-k-gons.pdf

エプスタインらによる、最小周囲と、面積、内角の合計などの特定の制約に従う他の重み関数について、この問題を解決するアルゴリズムがありますが、タイトルには最小面積と書かれています（周囲については系5.3を参照）。

基本的な考え方は、次のような動的プログラミング手法です (セクション 4 の最初の数段落を読んでください)。

S が指定された点の集合で、Q が最小周囲長の k 個の点からなる凸包であるとします。

p1 を Q の最下点、p2 と p3 を船体上の反時計回りの次の点とします。

Q を三角形 p1p2p3 と k-1 点 Q' の凸包 (三角形 p1p2p3 と辺 p1p3 を共有する) に分解できます。

主な観測結果は、Q' が k-1 に対して最適であるということです。ここで、最下点は p1 であり、次の点は p3 であり、Q' のすべての点は線 p2->p3 の同じ側にあります。

したがって、次のように、各四重極 (pi、pj、pk、m) に対して最適なポリゴンの 4 次元配列を維持します。

  • 多角形は、S のちょうど m 個の点からなる凸包です。
  • pi は、多角形の最下点です。
  • pj は反時計回りの次の頂点です。
  • 多角形のすべての点は線 pi -> pj の左側にあります。
  • すべての点は、pj->pk の pi と同じ側にあります。

m <= k-1 の最適なポリゴンが与えられた場合、m=k の最適なポリゴンを見つけるのに役立ちます。

この論文では、指定された空間と時間の境界を達成するためにそれを行う方法を正確に説明しています。

それが役立つことを願っています。

于 2010-06-22T06:02:00.217 に答える
2

それは正確にはかなりの解決策ではありません。実際、実装するのはかなり面倒ですが、確かに多項式の複雑さが増します。複雑さも大きいですが (n^5*k は私の概算です)、誰かがそれを改善する方法を見つけたり、ここでより良い解決策のアイデアを見つけたりするかもしれません。または、それで十分かもしれません。この複雑さでさえ、ブルートフォースよりもはるかに優れています。

注S:ハルを使用した最適解 (セット) にHは、元のセット内のすべてのポイントが含まれますH。そうしないと、 の境界点の 1 つを破棄してH、その欠落した点を含めて、周囲を減らすことができます。
( 「最適化」mbeckishの投稿と同じように更新)

仮定: セットからの 2 つの点が垂直線を形成しない。座標の原点を中心に不合理な角度で点のセット全体を回転させることで簡単に実現できます。

上記の仮定により、複雑なハルには左端と右端に 1 つのポイントがあります。また、この2点で船体をパーツに分けていtopますbottom。

topでは、この船体のパーツからセグメントを 1 つと、パーツからセグメントを 1 つ取り出しますbottom。middle segmentsこれらの 2 つのセグメントと、この船体の右側の部分の境界を境界と呼びましょうright。
注: これら 2 つのセグメントは、凸包の右側部分を左側に構築し続けるために知っておく必要があるすべてです。しかし、4 点ではなく 2 点だけでは十分ではありません。この方法では「凸性」の条件を維持できませんでした。

解決へと導きます。iポイント {p0, p1, p2, p3} と数値(i <= k)の各セットについて、right[p0, p1]、[p2, p3] が 2 つのmiddleセグメントでありi、このソリューションの一部のポイントright（境界線だけでなく、その内部のものも含む）。

右から左にすべてのポイントを通過します。新しい点ごとに、点 p がこの船体を左側 (またはパーツ上)pに継続できるように、点 {p​​0、p1、p2、p3} のすべての組み合わせをチェックします。そのような set と size ごとに、最適な周囲サイズが既に保存されています (上記の段落を参照)。topbottomi

注:ポイント {p0, p1, p2, p3} で形成されたポイントにポイントpを追加する場合、セット サイズを少なくとも 1 増やします。ただし、この数が 1 を超える場合もあります。三角形 {p, p0, p2}。船体の上ではなく、船体の中にあります。right-hulli

アルゴリズムは終わりです :) さらに、恐ろしく複雑ですが、すべてのセグメント [p0, p1]、[p2, p3] がmiddleセグメントであるとは限らないことに注意してください: 実際の計算時間を大幅に短縮するはずです。

更新これは、セット自体ではなく、最適な周囲サイズのみを提供します。しかし、セットを見つけるのは簡単です。上記の「状態」ごとに、周囲のサイズだけでなく、最後に追加されたポイントも保存します。次に、ソリューションを「トレース」できます。それは非常に標準的なトリックです。あなたにとっては問題ではないと思います。あなたはアルゴリズムが得意なようです:)

update2 これは本質的に DP (動的プログラミング) であり、少し肥大化しただけです

于 2010-06-21T19:58:48.133 に答える
1

考えられる最適化の 1 つ: サブセットにない点が凸包に含まれるサブセットは無視できます。

証拠：

凸包にサブセットにない点が含まれている場合は、包にあるサブセットから点を削除し、それを包の内部の点に置き換えます。これにより、周囲が同じかそれよりも小さい船体が得られます。

于 2010-06-21T19:35:38.940 に答える
-2

平面の場合、ジャービス マーチと呼ばれるアルゴリズムを使用できます。このアルゴリズムは、最悪の場合の複雑さが O(n^2) になります。このアルゴリズムでは、任意のポイントでハルの構築を開始し、次にどのポイントを追加する必要があるかを確認します。ウィキペディアから取得した疑似コード:

jarvis(S)
   pointOnHull = leftmost point in S
   i = 0
   repeat
      P[i] = pointOnHull
      endpoint = S[0]         // initial endpoint for a candidate edge on the hull
      for j from 1 to |S|-1
         if (S[j] is on left of line from P[i] to endpoint)
            endpoint = S[j]   // found greater left turn, update endpoint
      i = i+1
      pointOnHull = endpoint
   until endpoint == P[0]      // wrapped around to first hull point

私が理解している限りでは、凸包は点の集合ごとに固有であるため、最小値を見つける必要はありません。1つを見つけるだけで、定義上最小のものになります。

編集

投稿された解は、最も少ない点数で凸包を解きます。より多くのポイントを持つ船体は、より長い周囲を持ちます.Kポイントのセットの最小周囲ではなく、最小周囲を求めるという質問を誤解しました.

この新しい問題はおそらく NP であると考えられ、最長パスの問題に最もよく似ています。残念ながら、私には価値のある削減を提供するための工夫が欠けています。

于 2010-06-21T18:41:05.123 に答える