凸層

計算幾何学では、ユークリッド平面上の点の集合の凸層は、点を頂点とする入れ子になった凸多角形の列である。最も外側の層は点の凸包であり、残りは同様に再帰的に形成される。最も内側の層は退化していて、1つまたは2つの点のみで構成されることがある。^{[1]凸層を構築する問題は}、タマネギの皮むきまたはタマネギ分解 とも呼ばれる。^[2]

凸包を繰り返し見つけることで凸層を構築すると遅くなりますが、任意の点集合を時間内に凸層に分割することは可能です。^[1] $n$ $O(n\log n)$

凸層の初期の応用はロバスト統計学において、外れ値を識別し、サンプル点の集合の中心傾向を測定する方法であった。 ^[3]^[4]この文脈では、与えられた点を囲む凸層の数は凸包剥離深度と呼ばれ、凸層自体はデータ深度の概念における深度等高線である。^[5]

凸層は、クエリ半平面内のすべての点をリストするための効率的な範囲報告データ構造の一部として使用できます。各連続レイヤーの半平面内の点は、半平面の方向で最も極端な点を見つけるためのバイナリ検索によって見つけられ、そこから順番に検索されます。分数カスケーディングを使用すると、バイナリ検索を高速化し、一連の点を見つけるための合計クエリ時間を提供できます。^[6] $O(\log n+k)$ $k$ $n$

グリッド上の点には凸状の層があり^[7] 、凸形状内には均一にランダムな点が同じ数だけ存在します^{[8] 。} $n\times n$ $\Theta (n^{4/3})$

参考文献

^ ab Chazelle, Bernard (1985)、「平面集合の凸層について」、IEEE Trans. Inf. Theory、31 (4): 509–517、CiteSeerX 10.1.1.113.8709、doi :10.1109/TIT.1985.1057060、MR 0798557
^ Löffler, Maarten; Mulzer, Wolfgang (2014)、「タマネギの結合: 高速タマネギ分解のための不正確な点の前処理」、Journal of Computational Geometry、5 (1): 1–13、arXiv : 1302.5328、doi :10.20382/jocg.v5i1a1、MR 3162956、S2CID 6679520。
^ Barnett, V. (1976)、「多変量データの順序付け」、J. Roy. Statist. Soc. Ser. A、139 (3): 318–355、doi :10.2307/2344839、JSTOR 2344839、MR 0445726、S2CID 117008915
^ Eddy, WF (1982)、「凸包剥離」、COMPSTAT 1982 第 5 回シンポジウム、トゥールーズ 1982、Physica-Verlag、pp. 42–47、doi :10.1007/978-3-642-51461-6_4、ISBN 978-3-7051-0002-2
^ Liu, Regina Y. ; Parelius, Jesse M.; Singh, Kesar (1999)、「データ深度による多変量解析: 記述統計、グラフィックス、推論」、Annals of Statistics、27 (3): 783–858、doi : 10.1214/aos/1018031260、MR 1724033
^ シャゼル、バーナード;ギバス、レオ J. ;リー、DT (1985)、「幾何学的双対性の力」、BIT、25 (1): 76–90、doi :10.1007/BF01934990、MR 0785806
^ Har-Peled, Sariel ; Lidický, Bernard (2013)、「グリッドの剥離」、SIAM Journal on Discrete Mathematics、27 (2): 650–655、arXiv : 1302.3200、doi :10.1137/120892660、MR 3040367、S2CID 15837161
^ ダラル、ケタン (2004)、「タマネギを数える」、ランダム構造とアルゴリズム、24 (2): 155–165、doi :10.1002/rsa.10114、MR 2035873、S2CID 10366666

[c85-1] Chazelle, Bernard (1985)、「平面集合の凸層について」、IEEE Trans. Inf. Theory、31 (4): 509–517、CiteSeerX 10.1.1.113.8709、doi :10.1109/TIT.1985.1057060、MR 0798557

[2] Löffler, Maarten; Mulzer, Wolfgang (2014)、「タマネギの結合: 高速タマネギ分解のための不正確な点の前処理」、Journal of Computational Geometry、5 (1): 1–13、arXiv : 1302.5328、doi :10.20382/jocg.v5i1a1、MR 3162956、S2CID 6679520。

[3] Barnett, V. (1976)、「多変量データの順序付け」、J. Roy. Statist. Soc. Ser. A、139 (3): 318–355、doi :10.2307/2344839、JSTOR 2344839、MR 0445726、S2CID 117008915

[4] Eddy, WF (1982)、「凸包剥離」、COMPSTAT 1982 第 5 回シンポジウム、トゥールーズ 1982、Physica-Verlag、pp. 42–47、doi :10.1007/978-3-642-51461-6_4、ISBN 978-3-7051-0002-2

[5] Liu, Regina Y. ; Parelius, Jesse M.; Singh, Kesar (1999)、「データ深度による多変量解析: 記述統計、グラフィックス、推論」、Annals of Statistics、27 (3): 783–858、doi : 10.1214/aos/1018031260、MR 1724033

[6] シャゼル、バーナード;ギバス、レオ J. ;リー、DT (1985)、「幾何学的双対性の力」、BIT、25 (1): 76–90、doi :10.1007/BF01934990、MR 0785806

[7] Har-Peled, Sariel ; Lidický, Bernard (2013)、「グリッドの剥離」、SIAM Journal on Discrete Mathematics、27 (2): 650–655、arXiv : 1302.3200、doi :10.1137/120892660、MR 3040367、S2CID 15837161

[8] ダラル、ケタン (2004)、「タマネギを数える」、ランダム構造とアルゴリズム、24 (2): 155–165、doi :10.1002/rsa.10114、MR 2035873、S2CID 10366666