あなたの質問のタイトルにもかかわらず、実際には、直線的な多角形の長方形への最小の分割を探していると思います。(ジェイソンのリンクは、長方形による最小カバーに関するもので、これはまったく別の問題です。)
David Eppsteinは、2010 年の調査記事Graph-Theoretic Solutions to Computational Geometry Problemsのセクション 3 でこの問題について議論し、mathoverflow.net のこの回答で素晴らしい要約を提供しています。
アイデアは、端点として 2 つの凹面頂点を持ち、それらに沿って分割し、残りの凹面頂点ごとにもう 1 つの分割を形成する、互いに素な軸平行対角線の最大数を見つけることです。互いに素な軸平行対角線の最大数を見つけるには、対角線の交差グラフを作成します。このグラフは 2 部グラフであるため、その最大独立集合は、グラフ マッチング手法によって多項式時間で見つけることができます。
Eppstein の記事の図 2 を使用して、この見事に簡潔な説明をまとめます。おそらく穴のある直線的な多角形があるとします。
多角形を四角形に分割する場合、各凹頂点は、分割の少なくとも 1 つのエッジと一致する必要があります。したがって、これらのエッジのできるだけ多くが 2 つの役割を果たしている場合、つまり 2 つの凹状の頂点を接続している場合、最小の分割が得られます。
それでは、ポリゴン内に完全に含まれる 2 つの凹面頂点の間に軸平行な対角線を描きましょう。(「軸平行」とは、ここでは「水平または垂直」を意味し、ポリゴンの対角線は、隣接しない 2 つの頂点を結ぶ線です。) これらの線をできるだけ多く使用したいと考えています。交わらない。
(軸に平行な対角線がない場合、分割は簡単です。各凹状の頂点からカットを作成するだけです。または、軸に平行な対角線の間に交差がない場合は、それらすべてを使用し、残りの各凹状の頂点からカットします。 . それ以外の場合は、読み進めてください。)
一連の線分の交差グラフには、線分ごとにノードがあり、線が交差する場合、エッジは 2 つのノードを結合します。軸に平行な対角線の交点グラフは次のとおりです。
これは、一方の部分に垂直方向の対角線があり、もう一方の部分に水平方向の対角線がある 2 部構成です。ここで、対角線が交差しない限り、できるだけ多くの対角線を選択したいと考えています。これは、交差グラフで最大の独立集合を見つけることに対応します。
一般的なグラフで最大独立集合を見つけることは NP 困難な問題ですが、2 部グラフの特殊なケースでは、ケーニッヒの定理は、多項式時間で解くことができる最大マッチングを見つける問題と同等であることを示しています。Hopcroft–Karp アルゴリズムによる例。特定のグラフには複数の最大一致がある場合がありますが、それらはすべて同じサイズであるため、どれでも一致します。この例では、すべての最大一致には、{(2, 4), (6, 3), (7, 8)} のように 3 つの頂点のペアがあります。
(このグラフのその他の最大一致には、{(1, 3), (2, 5), (7, 8)}; {(2, 4), (3, 6), (5, 7)}; および { (1, 3), (2, 4), (7, 8)}.)
最大マッチングから対応する最小頂点カバーまで取得するには、ケーニッヒの定理の証明を適用します。上記のマッチングでは、左側のセットはL = {1, 2, 6, 7}、右側のセットはR = {3, 4, 5, 8}、 L内の一致 しない頂点のセットはU = { 1}。Uで始まる交互パスは 1 つだけ、つまり 1–3–6 であるため、交互パスの頂点のセットはZ = {1, 3, 6} であり、最小頂点カバーはK = ( L \ Z ) ∪です。 ( R ∩ <em>Z) = {2, 3, 7}、下に赤で示し、最大独立集合を緑で示します。
これを解剖の問題に戻すと、これは解剖で 5 つの軸平行対角線を使用できることを意味します。
最後に、残りの各凹面頂点から切り取りを行い、解剖を完了します。
