中心点（ジオメトリ）

統計学と計算幾何学において、中心点の概念は 、高次元ユークリッド空間のデータに中央値を一般化したものである。 d次元空間の点の集合が与えられたとき、その集合の中心点とは、その点を通る超平面によって点の集合が 2 つのほぼ等しい部分集合に分割される点である。小さい方の部分には、少なくとも 1/( d  + 1) の割合の点が含まれる必要がある。中央値と同様に、中心点はデータ点の 1 つである必要はない。空でない点の集合 (重複なし) には、必ず少なくとも 1 つの中心点が存在する。

密接に関連する概念として、点のTukey 深度(点を通る超平面の片側にあるサンプル点の最小数) と点集合のTukey 中位数(Tukey 深度を最大化する点) があります。中心点は深さが少なくともn /( d + 1) の点であり、Tukey 中位数は中心点である必要がありますが、すべての中心点が Tukey 中位数であるとは限りません。どちらの用語もJohn Tukey にちなんで名付けられました。

中央値をより高次元に一般化した別の例については、幾何中央値を参照してください。

中心点の存在は、ヘリーの定理を使って簡単に証明できます。n個の点があり、dn /( d  + 1) 個を超える点を含む閉じた半空間の族を考えます。 これらの半空間のいずれからも除外される点はn /( d + 1) 個未満なので、これらの半空間のd  + 1 個の部分集合の交差は空でなければなりません。ヘリーの定理により、これらすべての半空間の交差も空でなければならないことがわかります。この交差内の任意の点は、必ず中心点になります。

ユークリッド平面上の点については、中心点は線形時間で構築できる。^[1]任意の次元dにおいて、テューキーの中点（したがって中心点も）は O( n ^{d  − 1}  +  n  log  n ) の時間で構築できる。^[2]

d  + 2点の集合をラドン点に繰り返し置き換えるランダム化アルゴリズムは、そのTukey深度がサンプルセットのサイズに線形であり、次元の多項式の時間量で、任意の点集合の中心点の近似値を計算するのに使用できます。^{[3] [4]}

• Chan, Timothy M. (2004)、「最大 Tukey 深度のための最適なランダム化アルゴリズム」、Proc. 15th ACM–SIAM Symp. on Discrete Algorithms (SODA 2004)、Society for Industrial and Applied Mathematics、pp. 430–436、ISBN 978-0-89871-558-3。
• Clarkson, Kenneth L. ; Eppstein, David ; Miller, Gary L. ; Sturtivant, Carl ; Teng, Shang-Hua (1996 年 9 月)、「反復ラドン ポイントによる中心点の近似」(PDF)、International Journal of Computational Geometry & Applications、6 (3): 357–377、doi :10.1142/S021819599600023X、MR  1409651。
• エデルスブルンナー、ハーバート（1987）、組合せ幾何学におけるアルゴリズム、ベルリン：シュプリンガー・フェアラーク、ISBN 0-387-13722-X。
• Jadhav, S.; Mukhopadhyay, A. (1994)、「有限平面点集合の中心点を線形時間で計算する」、離散および計算幾何学、12 (1): 291–312、doi : 10.1007/BF02574382。
• Har-Peled, S.; Jones, M. (2020-12-31)、「点集合の中心への旅」、ACM Transactions on Algorithms、17 (1): 9:1–9:21、doi :10.1145/3431285、ISSN  1549-6325。