モーメント曲線

幾何学において、モーメント曲線は、 d次元ユークリッド空間における代数曲線であり、次の形式の直交座標を持つ点の集合によって与えられる。

\left(x,x^{2},x^{3},\dots ,x^{d}\right).

^[1]

ユークリッド平面では、モーメント曲線は放物線であり、3次元空間ではねじれた3次曲線です。射影空間での閉包は有理正規曲線です。

モーメント曲線は、巡回多面体、3つが一列に並ばない問題、クネーザーグラフの彩色数の幾何学的証明など、離散幾何学におけるさまざまな応用に使用されてきました。

プロパティ

すべての超平面は、モーメント曲線と最大d個の点で交差します。超平面が曲線とちょうどd個の点で交差する場合、曲線は各交差点で超平面と交差します。したがって、モーメント曲線上のすべての有限点集合は、アフィン一般位置にあります。^[2]

アプリケーション

モーメント曲線上の任意の有限点集合の凸包は、巡回多面体である。^[3]巡回多面体は、与えられた頂点数に対して可能な限り最大の面数を持ち、4次元以上では、その辺が完全グラフを形成するという性質を持つ。より強い意味では、それらは近隣多面体であり、つまり、最大でd /2 個の頂点からなる多面体の各集合が、その面の1つを形成する。モーメント曲線上の点集合は、d次元のn点集合のすべての可能なドロネー三角形分割の中で、単体の最大可能数も実現する。^[4] $\Omega (n^{\lceil d/2\rceil })$

ユークリッド平面では、ハムサンドイッチ定理を用いて、任意の面積または測定値を 4 つの等しい部分集合に分割することができます。同様に、より複雑に、3 次元の任意の体積または測定値を 3 つの平面によって 8 つの等しい部分集合に分割することができます。ただし、この結果は 5 次元以上には一般化されません。モーメント曲線は、d超平面によって 2 ^d部分集合に分割できない集合の例を提供しているためです。特に、5 次元では、5 つの超平面の集合は、モーメント曲線のセグメントを最大 26 個の部分に分割できます。4 次元を 4 つの超平面で 16 個の等しい部分集合に分割することが常に可能かどうかは不明ですが、4 次元モーメント曲線上の 16 個の点を 4 つの超平面の集合の 16 個の直交座標に分割することは可能です。^[5]

モーメント曲線に基づく構成は、任意の正の整数kとdに対して、 d 次元球面上に 2 k + d 個の点を配置し、すべての開いた半球に少なくとも k 個の点が含まれるようにすることが可能であるという 、 ゲールの補題を証明するために使用できます。この補題は、クネーザーグラフの彩色数を計算するために使用できます。この問題は、最初にLászló Lovászによって別の方法で解決されました。^[6]

モーメント曲線はグラフ描画にも使用され、すべてのn頂点グラフは、辺の長さがO( n )の3次元整数グリッド内に頂点を描き、2つの辺が交差しないことを示す。基本的な考え方は、 nより大きい素数pを選択し、グラフの頂点iを座標に配置することである。

（i , i ² mod p , i ³ mod p）^[7]

すると、平面は曲線と3か所でしか交差できない。交差する2つの辺は、同じ平面に4つの頂点を持つ必要があるため、このようなことは起こり得ない。素数を法とするモーメント曲線を使った同様の構成だが、3次元ではなく2次元で、3つが一列に並んでいない問題の線形境界が得られる。^[8]

注記

^ Matoušek (2002)、定義 5.4.1、p. 97; Matoušek (2003)、定義 1.6.3、p. 17.
^ エーデルスブルナー (1987)、p. 100; Matoušek (2002)、補題 5.4.2、p. 97; Matoušek (2003)、補題 1.6.4、p. 17.
^ ゲイル (1963);エーデルスブルナー (1987)、p. 101; Matoušek (2002)、補題 5.4.2、p. 97.
^ アメンタ、アタリ＆デビラーズ (2007)。
^ エーデルスブルナー (1987)、70–79 ページ。マトウシェク (2003)、50–51 ページ。
^ Matoušek (2003)、第3.5節、Galeの補題とSchrijverの定理、pp. 64–67。色付け問題におけるGaleの補題の使用は、Bárány (1978)によるものです。
^ コーエンら（1997）。
^ Roth (1951) によってPaul Erdősに帰属。

参考文献

アメンタ、ニーナ、アタリ、ドミニク、デビラー、オリヴィエ (2007)、「低次元多面体上の点に対するドロネー三角形分割の複雑性」、第 18 回 ACM-SIAM 離散アルゴリズムシンポジウム議事録、ニューヨーク: ACM、pp. 1106–1113、MR 2485262。
Bárány, I. (1978)、「クネザー予想の簡潔な証明」、Journal of Combinatorial Theory、シリーズ A、25 (3): 325–326、doi :10.1016/0097-3165(78)90023-7、MR 0514626。
Cohen, RF; Eades, P .; Lin, Tao; Ruskey, F. (1997)、「3次元グラフ描画」、Algorithmica、17 (2): 199–208、doi :10.1007/BF02522826、MR 1425733。
エデルスブルンナー、ハーバート（1987）、組合せ幾何学におけるアルゴリズム、EATCS理論計算機科学モノグラフ、第10巻、ベルリン：シュプリンガー・フェアラーク、ISBN 3-540-13722-X、MR 0904271。
ゲイル、デイビッド(1963)、「近隣多面体と巡回多面体」、クリー、ビクター(編)、凸性、シアトル、1961 年、純粋数学シンポジウム、第 7 巻、プロビデンス、ロードアイランド州: アメリカ数学協会、pp. 225–232、MR 0152944。
Matoušek、Jiří (2002)、離散幾何学講義、数学大学院テキスト、vol. 212、シュプリンガー・フェルラーグ、ISBN 978-0-387-95373-1。
Matoušek, Jiří (2003)、「Borsuk-Ulam 定理の使用: 組合せ論と幾何学における位相的手法の講義」、Universitext、Springer、ISBN 978-3-540-00362-5。
ロス、KF (1951)、「ハイルブロンの問題について」、ロンドン数学会誌、26 (3): 198–204、doi :10.1112/jlms/s1-26.3.198。

[1] Matoušek (2002)、定義 5.4.1、p. 97; Matoušek (2003)、定義 1.6.3、p. 17.

[2] エーデルスブルナー (1987)、p. 100; Matoušek (2002)、補題 5.4.2、p. 97; Matoušek (2003)、補題 1.6.4、p. 17.

[3] ゲイル (1963);エーデルスブルナー (1987)、p. 101; Matoušek (2002)、補題 5.4.2、p. 97.

[4] アメンタ、アタリ＆デビラーズ (2007)。

[5] エーデルスブルナー (1987)、70–79 ページ。マトウシェク (2003)、50–51 ページ。

[6] Matoušek (2003)、第3.5節、Galeの補題とSchrijverの定理、pp. 64–67。色付け問題におけるGaleの補題の使用は、Bárány (1978)によるものです。

[7] コーエンら（1997）。

[8] Roth (1951) によってPaul Erdősに帰属。