不透明セット

もし${\displaystyle K}$が被覆される有界凸集合である場合、その境界${\displaystyle \partial K}$周囲の長さが不透明な集合を形成する${\displaystyle |\partial K|}$したがって、不透明な集合の最短の長さは、最大でも周囲長です。${\displaystyle K}$厳密に凸であるということは、境界上に線分が存在しないことを意味します。内部バリアの場合、この境界は厳密です。境界上のすべての点は不透明集合に含まれなければなりません。なぜなら、境界上のすべての点には、他の点によって遮られることのない接線があるからです。 ^{[ 5 ]}同じ推論により、凸多角形の内部バリアの場合、すべての頂点が含まれなければならないことがわかります。したがって、頂点の最小シュタイナー木は最短の連結不透明集合であり、頂点の巡回セールスマンパスは最短の単一曲線不透明集合です。^{[ 4 ]}ただし、厳密に凸ではない非多角形の凸集合の内部バリア、または連結する必要のないバリアの場合、他の不透明集合が短くなる可能性があります。たとえば、境界の最長の線分を省略することは常に可能です。これらの場合、周囲長またはシュタイナー木の長さが不透明集合の長さの上限を提供します。 ^{[ 3 ] [ 4 ]}

任意の凸集合に対して不透明集合であることを証明するいくつかの証明がある。${\displaystyle K}$全長は少なくとも${\displaystyle |\partial K|/2}$周長の半分。最も単純なものの1つはクロフトン公式であり、それによると、任意の曲線の長さは、直線上の適切な確率分布からのランダムな直線との交点の期待値に比例する。問題を近似することで簡略化するのが便利である。${\displaystyle K}$厳密に凸な上位集合によって、その周囲長は元の集合に任意に近づけることができる。次に、接線を除いて、${\displaystyle K}$（全線のうちごくわずかな割合を占める）交差する線${\displaystyle K}$境界線を2回横切る。したがって、ランダムな線が交差する場合${\displaystyle K}$確率で${\displaystyle p}$境界を越える回数の期待値は${\displaystyle 2p}$しかし、交差する各線は${\displaystyle K}$不透明集合と交差するため、不透明集合との交差の期待値は少なくとも${\displaystyle p}$これは少なくともその半分です${\displaystyle K}$クロフトンの公式によれば、境界と障壁の長さは、これらの期待値と同じ比率になります。^{[ 6 ]}

この下限は${\displaystyle |\partial K|/2}$不透明集合の長さに関する下限は、定数係数が 1/2 より大きい値に改善することはできません。なぜなら、長さがこの下限に近い不透明集合を持つ凸集合の例が存在するからです。特に、非常に細長い長方形の場合、1 つの長い辺と 2 つの短い辺が障壁を形成し、その全長は周囲長の半分に任意に近づけることができます。したがって、被覆領域の周囲長のみを考慮した下限の中で、${\displaystyle |\partial K|/2}$可能な限り最善である。^{[ 6 ]}しかし、${\displaystyle |\partial K|/2}$このように、単一の形状だけでなく一連の形状を考慮する必要がある。なぜなら、任意の凸集合に対して${\displaystyle K}$それは三角形ではない、${\displaystyle \delta }$すべての不透明集合の長さが少なくとも${\displaystyle |\partial K|/2+\delta }$[ ^{7 ]​}

三角形の場合、任意の凸多角形と同様に、最短連結不透明集合は最小シュタイナー木である。^{[ 8 ]}三角形の場合、この木は明示的に記述できる。三角形の最も広い角が${\displaystyle 2\pi /3}$（120°）以上の場合は三角形の最短辺2本を使用し、それ以外の場合は頂点から三角形のフェルマー点までの3本の線分で構成されます。 ^{[ 9 ]}ただし、連結性を仮定しない場合、シュタイナー木の最適性は証明されていません。泉は正三角形の周長半減下限をわずかに改善したことを証明しました。^{[ 10 ]}

単位正方形の場合、周囲長は 4、周囲長から最長辺を引いた値は 3、最小シュタイナー木の長さは$1+√3 ≈ 2.732$しかし、長さが短い、分断された不透明な森が知られている。$\displaystyle {\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639}$これは、正方形の3つの頂点の最小シュタイナー木と、4番目の頂点を中心に接続する線分から構成されます。ロス・ホンズバーガーは、この発見をカナダの教師モーリス・ポワリエに帰していますが^{[ 11 ]}、1962年と1964年には既にジョーンズによって記述されていました^{[ 12 ] [ 13 ]} 。これは、2つのコンポーネントのみを持つ森の中で最適であることが知られており^{[ 5 ] [ 14 ]}、より一般的には最良のものであると推測されていますが、これはまだ証明されていません^{[ 7 ]} 。ジョーンズによって既に証明されている正方形の周長半減下限2 ^{[ 12 ] [ 13 ]}は、わずかに改善され、${\displaystyle 2.00002}$可算個の可測曲線で構成される任意の障壁に対して、^{[ 7 ]}障壁を与えられた正方形の近くにのみ配置するという、以前の同様の境界を改善した。^{[ 6 ]}

単位円のケースは、 1995年のサイエンティフィック・アメリカン誌のコラムでイアン・スチュワートによって説明され、長さの解が示されました。${\displaystyle 2+\pi }$、^{[ 15 ]}単一の曲線または連結された障壁には最適であるが^{[ 8 ] [ 16 ] [ 17 ]}、複数の曲線を持つ不透明な森には最適ではない。ヴァンス・ファーバーとヤン・ミシエルスキは、この単一曲線解を1974年にメナヘム・マジドールに帰している。 ^{[ 8 ]} 1980年までに、E.マカイはすでに長さが約 3 成分のより良い解を提供していた。${\displaystyle 4.7998}$[ ^{18 ]}スチュワートのコラムの続編でジョン・デイによって再発見された。^{[ 19 ]}最適解の未知の長さはビーム検出定数^と呼ばれている。^{[ 20 ]}

周囲長に関する不透明フォレストの長さの一般的な上限によれば、凸集合の周囲長は、その最短不透明フォレストの長さを2倍以内の精度で近似します。Dumitrescu、Jiang、Pach、およびTóthは、2つの論文で、凸多角形の最短不透明集合に対するいくつかの線形時間近似アルゴリズムを提供しており、その近似比は2よりも優れています。

• 一般的な不透明集合に対して、彼らは近似比が最大で$$\displaystyle {\frac {1}{2}}+{\frac {2+{\sqrt {2}}}{\pi }}\approx 1.5868.}$$このアルゴリズムの基本的な考え方は、入力の最小周長境界ボックスから「弓矢」のような障壁を構築することです。これは、境界ボックスの1つの角から反対側の角まで多角形を囲むように伸びる多角形の鎖と、境界ボックスの3番目の角からボックスの対角線に接続する線分で構成されます。^{[ 4 ]}
• 単一の弧からなる不透明集合の場合、近似比が最大で$$\displaystyle {\frac {\pi +5}{\pi +2}}\approx 1.5835.}$$結果として得られるバリアは、入力形状の支持線によって定義されます。入力はこの線上の区間に垂直に投影され、バリアはこの区間の両端を、円の最適な連結バリアのように、入力の周囲にぴったりと引き伸ばされたU字型の曲線で結びます。このアルゴリズムは、回転キャリパーを使用して、結果として得られるバリアの長さが最小になる支持線を見つけます。^{[ 4 ]}
• 連結した不透明集合に対して、彼らは近似比が最大で${\displaystyle 1.5716}$この方法は、単一弧バリアと、正三角形に近い形状に対する特別な処理を組み合わせたもので、正三角形のシュタイナー木はより短い連結バリアとなる。^{[ 4 ]}
• 内部障壁については、近似比が最大で${\displaystyle 1.7168}$[ ^{24 ]このアイデアは、Shermer が提案した、}以前の誤ったアルゴリズムの構造の一般化 (点のサブセット上のシュタイナー木と、残りの入力の三角形分割のための高さセグメント) を使用し、^{[ 23 ]}近似のシュタイナー木の部分については高速近似を行うというものです。^{[ 24 ]}

さらに、凸多角形の最短連結内部バリアは最小シュタイナー木によって与えられるため、多項式時間近似スキームが存在する。^{[ 4 ]}

特定の森林が占める地域は、次のようにして決定できます。

• 森を構成する各連結成分の凸包を求めなさい。
• 各頂点について${\displaystyle p}$船体の周囲を円を描くように線を引いてください。${\displaystyle p}$平面を、スイープラインが船体のいずれかと交差するくさび形と、スイープラインが平面を障害物なく交差するくさび形に分割する。覆われたくさび形の結合によって、一連の${\displaystyle C_{p}}$。
• すべての集合の共通部分を見つける${\displaystyle C_{p}}$この交点は森林の被覆率を示しています。

入力が以下で構成されている場合${\displaystyle n}$線分を形成する${\displaystyle m}$接続されたコンポーネント、次に各${\displaystyle n}$セット${\displaystyle C_{p}}$最大で${\displaystyle 2m}$ウェッジ。したがって、被覆領域の組み合わせ的複雑さと、それを構築するのにかかる時間は、${\displaystyle O(m^{2}n^{2})}$ビッグオー記法で表すと。^{[ 25 ]}

このアルゴリズムは、入力のカバレッジ領域の組み合わせ的複雑度がこの上限に一致する最悪の場合には最適ですが、実際には、残りのすべてのハルが互いに素になるまで重複するハルのペアをマージする前処理フェーズによってヒューリスティックに改善できます。${\displaystyle O(n\log ^{2}n)}$入力が単一のハルに縮小される場合、よりコストのかかるスイープおよび交差アルゴリズムを実行する必要はありません。この場合、ハルがカバレッジ領域になります。^{[ 26 ]}