直交凸包

幾何学では、標準基底ベクトルの 1 つに平行なすべての直線Lについて、 KとLの交点が空、点、または単一の線分である場合、集合K ⊂ R ^dは直交凸であると定義されます。「直交」という用語は、異なる基底ベクトルが直交するユークリッド空間内の対応する直交基底と座標、および対応する直線を指します。通常の凸集合とは異なり、直交凸集合は必ずしも連結されているわけではありません。

集合K ⊂ R ^dの直交凸包は、 Kのすべての連結された直交凸超集合の共通部分です。

これらの定義は、古典的な凸性理論からの類推でなされます。古典的な凸性理論では、すべての直線Lについて、 KとLの交点が空、点、または単一の線分である場合に、 K は凸です。直交凸性は、この特性が保持される必要がある直線を制限するため、すべての凸集合は直交凸ですが、その逆は当てはまりません。同じ理由で、直交凸包自体は、同じ点集合の凸包の部分集合です。点p がKの直交凸包に属するのは、 p を頂点とする軸に沿った閉じた直交点のそれぞれがKと空でない交点を持つ場合のみです。

直交凸包は、直線凸包とも呼ばれ、2 次元では x - y凸包とも呼ばれます。

この図は、平面上の 16 個の点の集合と、これらの点の直交凸包を示しています。図からわかるように、直交凸包は、各座標方向の端の頂点を接続する退化したエッジを持つ多角形です。このような離散的な点集合の場合、直交凸包のすべてのエッジは水平または垂直です。この例では、直交凸包は接続されています。

凸包の同等の定義が複数存在する古典的な凸性とは対照的に、凸包の定義に類推して作成された直交凸包の定義は、異なる幾何学的オブジェクトをもたらします。これまでに、研究者は集合の直交凸包の次の 4 つの定義を検討してきました。 ${\displaystyle K\subset \mathbb {R} ^{d}}$

1. 最大値定義: この記事の冒頭で説明した定義。点集合の最大値に基づいています。
2. 古典的な定義: の直交凸包は、のすべての直交凸超集合の共通部分です。Ottmann、Soisalon-Soininen、Wood (1984)。${\displaystyle K}$${\displaystyle K}$
3. 連結定義: の直交凸包は、の連結された最小の直交凸超集合である; Nicholl et al. (1983)。${\displaystyle K}$${\displaystyle K}$
4. 関数定義: の直交凸包は、上にあるすべての非負直交凸関数の零点集合の共通部分です(Matoušek & Plecháč (1998))。${\displaystyle K}$${\displaystyle 0}$${\displaystyle K}$

右側の図では、上の図は平面上の 6 つの点の集合を示しています。点集合の古典的な直交凸包は、点集合そのものです。上から下に向かって、2 番目から 4 番目の図は、それぞれ点集合の最大直交凸包、連結直交凸包、機能直交凸包を示しています。ご覧のとおり、直交凸包は、いくつかの退化した「エッジ」、つまり、端の頂点を内角で結ぶ直交凸交互多角形チェーンを持つ多角形です。 ${\displaystyle 90^{\circ}}$

古典的な直交凸包は、次の凸包の定義に倣って、集合 の最小の直交凸集合として同義に定義できます。の凸包はの最小の凸集合です。古典的な直交凸包は切断されている可能性があります。点集合に、標準基底ベクトルの 1 つに平行な線上に点のペアがない場合、そのような点集合の古典的な直交凸包は、点集合自体に等しくなります。 ${\displaystyle K\subset \mathbb {R} ^{2}}$${\displaystyle K}$${\displaystyle K}$

凸包のよく知られた性質は、カラテオドリの定理から導かれます。つまり、ある点が点集合の凸包の内部にあるのは、その点がすでに の凸包または の 個以下の点内にある場合のみです。この性質は、古典的な直交凸包にも当てはまります。 ${\displaystyle x\in \mathbb {R} ^{d}}$${\displaystyle K\subset \mathbb {R} ^{d}}$${\displaystyle d+1}$${\displaystyle K}$

定義により、連結された直交凸包は常に連結されています。ただし、連結されているのは一意ではありません。たとえば、平面上の、水平線または垂直線上にない 2 つの点を考えてみましょう。このような点の連結された直交凸包は、点を内角で結ぶ直交凸交互多角形チェーンです。このような多角形チェーンはすべて同じ長さであるため、点集合には連結された直交凸包が無限に存在します。 ${\displaystyle 90^{\circ}}$

平面上の点集合の場合、連結直交凸包は最大直交凸包から簡単に得られます。点集合の最大直交凸包が連結されている場合、それは の連結直交凸包に等しくなります。そうでない場合、 の連結直交凸包は無限に存在し、各連結直交凸包は、 の最大直交凸包の連結成分を内角 の直交凸交互多角形鎖で結合することによって得られます。 ${\displaystyle K\subset \mathbb {R} ^{2}}$${\displaystyle K}$${\displaystyle K}$${\displaystyle K}$${\displaystyle 90^{\circ}}$

関数直交凸包は、集合の性質ではなく、集合に関する関数の性質を使用して定義されます。つまり、凸関数の概念を次のように制限します。関数は、標準基底ベクトルの非ゼロに平行な各線への制限が凸関数である場合に、直交凸と呼ばれます。 ${\displaystyle f:\mathbb {R} ^{d}\rightarrow \mathbb {R} }$

直交凸包を構築するためのアルゴリズムを研究した著者は数名います: Montuno & Fournier (1982); Nicholl et al. (1983); Ottmann, Soisalon-Soininen & Wood (1984); Karlsson & Overmars (1988)。これらの著者の結果によると、平面上のn点の直交凸包は、時間O ( n log  n )で構築できる可能性があります。整数座標を持つ点の整数検索データ構造を使用すると、さらに高速になる可能性があります。

直交凸性を制限配向凸性に一般化するのは自然であり、有限の傾きの集合のいずれかを持つすべての直線が連結された部分集合で K と交差しなければならない場合、集合 K は凸であると定義されます。たとえば、Rawlins (1987)、Rawlins and Wood (1987、1988)、または Fink and Wood (1996、1998) を参照してください。

さらに、有限計量空間のタイトスパンは直交凸包と密接に関係しています。平面上の有限点集合に連結された直交凸包がある場合、その包は点集合上のマンハッタン距離のタイトスパンとなり​​ます。ただし、直交包が連結されていない点集合や、より高次元のL ^p空間では、直交包とタイトスパンは異なります。

O'Rourke (1993)は、直交凸性と直交可視性に関する他のいくつかの結果を説明しています。

• Biswas, Arindam; Bhowmick, Partha; Sarkar, Moumita; Bhattacharya, Bhargab B. (2012)、「デジタル平面上のオブジェクトの直交包を見つけるための線形時間組み合わせアルゴリズム」、Information Sciences、216 : 176–195、doi :10.1016/j.ins.2012.05.029。
• Fink, Eugene; Wood, Derick (1996)、「制限方向凸性の基礎」(PDF)、Information Sciences、92 (1–4): 175–196、doi :10.1016/0020-0255(96)00056-4、S2CID  17771224。
• Fink, Eugene; Wood, Derick (1998)、「制限された方向の凸性における一般化された半空間」(PDF)、Journal of Geometry、62 (1–2): 99–120、doi :10.1007/BF01237603、S2CID  14709697。
• Karlsson, Rolf G.; Overmars, Mark H. (1988)、「グリッド上のスキャンラインアルゴリズム」、BIT、28 (2): 227–241、doi :10.1007/BF01934088、hdl : 1874/16270、S2CID  32964283。
• Matoušek, J.; Plecháč, P. (1998)、「機能的別凸包について」、離散および計算幾何学、19 (1): 105–130、doi : 10.1007/PL00009331。
• Montuno, DY; Fournier, A. (1982)、x - y多角形集合のx - y凸包の検出、技術レポート 148、トロント大学。
• Nicholl, TM; Lee, DT ; Liao, YZ; Wong, CK (1983)、「XY 多角形集合の XY 凸包について」、BIT、23 (4): 456–471、doi :10.1007/BF01933620、S2CID  10492640。
• オルーク、ジョセフ（1993）、C言語による計算幾何学、ケンブリッジ大学出版局、pp. 107-109。
• オットマン、T.; ソイザロン-ソイニネン、E.;ウッド、デリック(1984)、「直線凸包の定義と計算について」、情報科学、33 (3): 157–171、doi :10.1016/0020-0255(84)90025-2。
• ローリンズ、GJE (1987)、「制限された配向幾何学の探究」、博士論文および技術報告書 CS-87-57、ウォータールー大学。
• ローリンズ、GJE;ウッド、デリック(1987)、「有限方向凸包の最適計算」、情報と計算、72 (2): 150–166、doi : 10.1016/0890-5401(87)90045-9。
• Rawlins, GJE; Wood, Derick (1988)、「Ortho-convexity and its generalizations」、Toussaint, Godfried T. (ed.)、Computational Morphology、Elsevier、pp. 137–152 より。