不透明セット

離散幾何学において、不透明集合とは、多角形、円、またはその他の形状を横切るすべての視線を遮る平面上の曲線またはその他の集合のシステムである。不透明集合は、障壁、ビーム検出器、不透明カバー、または（線分またはその他の曲線の森の形をしている場合は）不透明森とも呼ばれる。不透明集合は、1916年にステファン・マズルキエヴィッチによって導入され、 ^[1] 1959年にフレデリック・バゲミルによってその全長を最小化する問題が提起された。^[2]

たとえば、単位正方形を通る可視性は、長さ 4 の 4 つの境界辺によってブロックされますが、より短い不透明な森が、長さ の正方形を横切る可視性をブロックします。これが正方形の最短の不透明集合であるかどうかは証明されておらず、他のほとんどの図形についても同様にこの問題は未解決のままです。平面内の任意の有界凸集合の最短の不透明集合の長さは、集合の周囲長以下で、少なくとも周囲の半分の長さです。正方形については、周囲の半分よりもわずかに強い下限が知られています。不透明集合がよく研究される別の凸集合は単位円で、その最短の連結不透明集合の長さは です。連結性を仮定しない場合、円の最短の不透明集合の長さは、少なくとも で、最大です。 ${\displaystyle {\sqrt {2}}+{\tfrac {1}{2}}{\sqrt {6}}\approx 2.639}$${\displaystyle 2+\pi }$${\displaystyle \pi}$${\displaystyle 4.7998}$

凸多角形の最短の不透明集合を求めるとされるいくつかの公開されたアルゴリズムは、後に誤りであることが示されました。それでも、近似比が保証された不透明集合を線形時間で見つけたり、与えられた線分系によって可視性がブロックされている平面のサブセットを多項式時間で計算したりすることは可能です。

平面上のすべての集合はのスーパーセットを通る可視性をブロックし、その被覆 はです。は、その点を通るすべての直線が と交差する点で構成されます。 与えられた集合がの被覆のサブセットを形成する場合、 はの不透明集合、バリア、ビーム検出器、または不透明カバーと呼ばれます。 さらに、が有限個の線分で構成され、 その和が森 を形成する特殊な形式を持つ場合、それは不透明森と呼ばれます。 与えられた任意の集合 （それ自体を含む）に対して、多くの不透明集合の可能性があり、多くの不透明森の可能性があります。 不透明森、またはより一般的には修正可能曲線のシステムの場合、その長さは標準的な方法で測定できます。 より一般的な点集合の場合、1 次元ハウスドルフ測度を使用でき、線分と修正可能曲線の場合の標準の長さと一致します。^[3]${\displaystyle S}$${\displaystyle S}$ ${\displaystyle C}$${\displaystyle C}$${\displaystyle S}$${\displaystyle K}$${\displaystyle S}$${\displaystyle S}$${\displaystyle K}$${\displaystyle S}$${\displaystyle K}$${\displaystyle K}$

この問題に関する研究のほとんどは、与えられた集合が凸集合であると仮定している。それが凸集合ではなく、単に連結された集合である場合、その不透明集合を変えずにその凸包で置き換えることができる。この問題のいくつかの変形では、不透明集合が の完全に内側か完全に外側にあるように制限される。この場合、それはそれぞれ内部障壁または外部障壁と呼ばれる。これが指定されていない場合、障壁はその場所に制約がないものとみなされる。不透明集合が連結されているか、単一の曲線を形成しなければならない問題のバージョンも検討されている。すべての凸集合に最短の不透明集合があるかどうか、またはその不透明集合の長さが下限値に達することなくそれに近づくかどうかはわかっていない。^{[3] の}不透明集合はどれも不透明森によって長さが任意に近い値に近似することができ、^{[4]あらゆる}凸多角形には不透明森が最短の不透明集合として存在すると推測されているが、これは証明されていない。^[3]${\displaystyle K}$${\displaystyle K}$ ${\displaystyle P}$${\displaystyle P}$

カバーされる領域が凸集合である場合、その最短の不透明集合の長さは、その周囲の半分以上、周囲長以下でなければなりません。一部の領域では、これらの境界をさらに改善することができます。

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

任意の凸集合の不透明集合の全長は、周囲の半分以上でなければならないという証明は複数あります。最も単純なものの 1 つは、クロフトンの公式です。この公式によれば、任意の曲線の長さは、直線上の適切な確率分布からのランダムな直線との交点の期待数に比例します。問題を簡略化するには、厳密に凸なスーパーセットで近似すると便利です。このスーパーセットは、周囲が元のセットに任意に近いように選択できます。すると、 への接線(すべての直線の消失分数を形成する) を除き、 と交差する直線は境界を 2 回交差します。したがって、ランダムな直線が確率 で交差する場合、境界交差の期待数は です。しかし、 と交差する各直線はその不透明集合と交差するため、不透明集合との交差の期待数は少なくとも で、これは の場合の少なくとも半分です。クロフトンの公式により、境界とバリアの長さは、これらの期待数と同じ比率を持ちます。^[6]${\displaystyle K}$${\displaystyle |\partial K|/2}$${\displaystyle K}$${\displaystyle K}$${\displaystyle K}$${\displaystyle K}$${\displaystyle p}$${\displaystyle 2p}$${\displaystyle K}$${\displaystyle p}$${\displaystyle K}$

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

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

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

単位円の場合は、 1995 年のScientific AmericanのIan Stewartのコラムで説明されており、長さ の解^[15]は、単一の曲線または連結された障壁^{[8] [16] [17]}には最適ですが、複数の曲線がある不透明な森には最適ではありません。Vance FaberとJan Mycielski は、この単一曲線の解を1974 年のMenachem Magidorによるものとしています。 ^[8] 1980 年までに、E. Makai は、長さがおよそ である、より優れた 3 成分解を既に提供しており、^[18]これは、Stewart のコラムのフォローアップで John Day によって再発見されました。^{[19]最適解の未知の長さは、}ビーム検出定数と呼ばれています。^[20]${\displaystyle 2+\pi }$${\displaystyle 4.7998}$

公開されている 2 つのアルゴリズムは、最適解が特別な構造を持つという考えに基づいて、任意の多角形に最適な不透明フォレストを生成すると主張しています。その構造とは、多角形の三角形分割における 1 つの三角形のシュタイナー木と、残りの各三角形の 1 つの頂点から反対側の辺までの線分 (長さは三角形の高さに等しい) です。この構造は、正方形の最適解の推測構造と一致します。この形式の解の最適な三角形分割はこれらのアルゴリズムの入力の一部ではありませんが、動的計画法を使用して多項式時間でアルゴリズムによって見つけることができます。^{[21] [22]}ただし、これらのアルゴリズムはすべての多角形の問題を正しく解決するわけではありません。一部の多角形には、見つかったものとは異なる構造を持つ短い解があるためです。特に、細長い長方形の場合、4 つの頂点すべての最小シュタイナー木は、これらのアルゴリズムが見つける三角形分割ベースの解よりも短くなります。^[23]実行時間に関係なく、問題の正しい解を見つけることが保証されている既知のアルゴリズムはありません。^[3]

この障害にもかかわらず、凸多角形の最短の単一曲線バリア（頂点の巡回セールスマン経路）は、根号の和が正確に計算できる計算モデルでは、動的計画法アルゴリズムによって凸多角形に対して多項式時間で正確に計算できます。^{[4]また、この問題の}近似アルゴリズムや、与えられたバリアの被覆率を決定するためのより成功した研究もあります。

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

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

さらに、凸多角形の最短連結内部障壁は最小シュタイナー木によって与えられるため、多項式時間近似スキームを持つ。^[4]

特定の森林がカバーする領域は次のように決定できます。

• フォレストの各接続コンポーネントの凸包を見つけます。
• 殻の各頂点について、 の周りを円形にスイープし、平面を、スイープ ラインが殻の 1 つと交差するウェッジと、スイープ ラインが障害物なしで平面と交差するウェッジに分割します。覆われたウェッジの和集合は、集合 を形成します。${\displaystyle p}$${\displaystyle p}$${\displaystyle C_{p}}$
• すべての集合の共通部分を見つけます。この共通部分が森林の被覆範囲です。${\displaystyle C_{p}}$

入力が連結成分を形成する線分で構成されている場合、各セットは最大でウェッジで構成されます。したがって、カバレッジ領域の組み合わせの複雑さと、それを構築する時間は、ビッグオー記法で表現されます。^[25]${\displaystyle n}$${\displaystyle m}$${\displaystyle n}$${\displaystyle C_{p}}$${\displaystyle 2m}$${\displaystyle O(m^{2}n^{2})}$

このアルゴリズムは、入力の被覆領域の組み合わせ複雑度がこの境界に一致する場合、最悪のケースでは最適ですが、実際には、重複する包のペアをマージして、残りの包がすべて分離するまで、時間内に行う前処理フェーズによって、経験的に改善できます。これにより入力が単一の包に削減された場合、よりコストのかかるスイープおよび交差アルゴリズムを実行する必要はありません。この場合、包が被覆領域です。^[26]${\displaystyle O(n\log^{2}n)}$

Mazurkiewicz (1916) は、不透明集合が非自明な曲線を一切含まずに、かつ有限の全長を持つことが可能であることを示した。^[1]図に示す Bagemihl (1959) の簡略化された構成は、単位正方形の例を生み出す。構成は、追加特性を持つ不透明集合を形成する線分から始まる。すなわち、負の傾きの線分は負でない傾きの線分をすべてブロックし、正の傾きの線分は正でない傾きの線分をすべてブロックする。図では、この特性を持つ最初の線分は、正方形の対角線に沿った 4 つの互いに素な線分である。次に、この特性を維持しながら、これらの線分を繰り返し細分化する。構成の各レベルで、各線分は、その中点付近の小さな隙間によって、同じ符号の傾きを持つ 2 つの線分に分割され、これらが合わさって、元の線分によってブロックされていた反対符号の線分をすべてブロックする。この構成の極限集合はカントール空間であり、これは構成のすべての中間段階と同様に、正方形の不透明集合である。ギャップサイズが急速に減少するにつれて、この構成はハウスドルフ次元が 1 で、1 次元ハウスドルフ測度(このような集合に適した長さの概念) が有限である集合を生成する。^[2]

正方形の境界の距離集合、または正方形の4つのセグメントからなる最短の不透明集合は、どちらも0から までの区間内のすべての距離を含みます。しかし、同様のフラクタル構造を使用することで、この区間内の距離の無限個を省略した距離集合を持つフラクタル不透明集合、または（連続体仮説を仮定して）測度ゼロの集合を形成するフラクタル不透明集合を見つけることも可能です。^[2]${\displaystyle {\sqrt {2}}}$

不透明集合は、もともと1916 年にStefan Mazurkiewiczによって研究されました。^{[1]不透明集合に関するその他の初期の研究には、1955 年の}HM Sen Guptaと NC Basu Mazumdarの論文^[27]や、1959 年のFrederick Bagemihlの論文^[2]がありますが、これらは主に距離集合と障壁の位相的特性に関するものであり、障壁の長さを最小化することに関するものではありません。Bagemihl は論文の追記で、正方形の内部障壁の最小の長さを求め^[2]、その後の研究は主に長さの最小化を含む問題のバージョンに焦点を当ててきました。それらの問題は、埋設されたまっすぐな電話ケーブルを見つけるためにできるだけ短い長さの溝を掘ること、^[8]森で迷ったときに近くのまっすぐな道を見つけようとすること、^[17]海で迷ったときにまっすぐな海岸線まで泳いで行くこと、^[4]ガラスの家を不透明にするために壁を効率的に塗装すること、^[28]など、 さまざまな多彩な定式化で繰り返し提起されてきました。

この問題は、リーマン多様体上のすべての測地線を遮る集合にも一般化されている^{[29] [30]}。また、高次元の集合を通る直線を遮る集合にも一般化されている。3次元では、対応する問題は、立体全体の可視性を遮る最小の総面積の面の集合を求めるものである。しかし、球体などの一部の立体では、そのような集合が存在するかどうか、またはその面積に到達できない下限値があるかどうかは明らかではない。 ^{[8] [31]}

• ベルマンの森で迷子になった問題
• ユークリッドの果樹園