距離幾何学

距離幾何学は、点対間の距離の与えられた値のみに基づいて点集合を特徴づけ、研究する数学の一分野である。 ^{[1] [2] [3]より抽象的に言えば、}半距離空間とそれらの間の等長変換の研究である。この観点から見ると、距離幾何学は一般位相幾何学の一分野とみなすことができる。^[4]

歴史的に、距離幾何学における最初の成果は、西暦1世紀のヘロンの公式です。現代理論は19世紀にアーサー・ケイリーの研究から始まり、20世紀にはカール・メンガーらによってより広範な発展を遂げました。

距離幾何学の問題は、生物学、^[4]センサーネットワーク、^[5]測量、航海、地図作成、物理学など、点間の距離から点の配置（相対位置）の形状を推測する必要があるときに発生します。

はじめにと定義

まず、2 つの特定の問題を説明することによって、距離幾何学の概念を説明します。

双曲線航法の問題

最初の問題:双曲線航法

位置が既知の3つの地上無線局A、B、Cを考えてみましょう。無線受信機の位置は不明です。無線信号がこれらの局から受信機まで到達するのにかかる時間 は不明ですが、時間差と は既知です。これらから距離差 と がわかり、そこから受信機の位置を特定することができます。 ${\displaystyle t_{A},t_{B},t_{C}}$ ${\displaystyle t_{A}-t_{B}}$ ${\displaystyle t_{A}-t_{C}}$ ${\displaystyle c(t_{A}-t_{B})}$ ${\displaystyle c(t_{A}-t_{C})}$

2番目の問題:次元削減

データ分析では、ベクトルとして表現されたデータのリストが与えられ、それらが低次元のアフィン部分空間内に存在するかどうかを調べる必要があることがよくあります。データの低次元表現には、記憶容量や計算時間の節約、データへのより深い洞察の提供など、多くの利点があります。 ${\displaystyle \mathbf {v} =(x_{1},\ldots ,x_{n})\in \mathbb {R} ^{n}}$

定義

ここで、問題を検討することによって自然に生じるいくつかの定義を形式化します。

半距離空間

,上の点のリストが与えられた場合、, のリストによって点のペア間の距離を任意に指定することができます 。これは半距離空間、すなわち三角不等式のない距離空間を定義します。 ${\displaystyle R=\{P_{0},\ldots ,P_{n}\}}$ ${\displaystyle n\geq 0}$ ${\displaystyle d_{ij}>0}$ ${\displaystyle 0\leq i<j\leq n}$

明示的に、半距離空間を、すべてのに対して、 ${\displaystyle R}$ ${\displaystyle d:R\times R\to [0,\infty )}$ ${\displaystyle x,y\in R}$

1. 正値:   の場合に限ります  。 ${\displaystyle d(x,y)=0}$ ${\displaystyle x=y}$
2. 対称性: . ${\displaystyle d(x,y)=d(y,x)}$

任意の距離空間は、より強く半距離空間である。特に、次元ユークリッド空間 は、距離幾何学における標準的な距離空間である。 ${\displaystyle \mathbb {R} ^{k}}$ ${\displaystyle k}$

距離が正であるという単なる要件以上の制約を距離に強制したくないため、定義では三角不等式は省略されています。 ${\displaystyle d_{ij}}$

実際には、半距離空間は不正確な測定から自然に生じます。例えば、直線上の3点が と与えられた場合、不正確な測定によって となり、三角不等式に違反する可能性があります。 ${\displaystyle A,B,C}$ ${\displaystyle d_{AB}=1,d_{BC}=1,d_{AC}=2}$ ${\displaystyle d_{AB}=0.99,d_{BC}=0.98,d_{AC}=2.00}$

等尺性埋め込み

2 つの半距離空間 が与えられた場合、からへの等長埋め込みは半距離を保存する写像、つまりすべての に対して となる写像です。 ${\displaystyle (R,d),(R',d')}$ ${\displaystyle R}$ ${\displaystyle R'}$ ${\displaystyle f:R\to R'}$ ${\displaystyle x,y\in R}$ ${\displaystyle d(x,y)=d'(f(x),f(y))}$

たとえば、上で定義した有限半距離空間を考えると、 からへの等長埋め込みは、すべての に対してとなる点 によって定義されます。 ${\displaystyle (R,d)}$ ${\displaystyle R}$ ${\displaystyle \mathbb {R} ^{k}}$ ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$ ${\displaystyle d(A_{i},A_{j})=d_{ij}}$ ${\displaystyle 0\leq i<j\leq n}$

アフィン独立性

点 が与えられたとき、任意の に対して の 1 次元アフィン部分空間内に収まらない場合、かつ が張る-単体が正の -体積を持つ場合、つまり である場合に限り、アフィン独立であると定義されます。 ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$ ${\displaystyle l}$ ${\displaystyle \mathbb {R} ^{k}}$ ${\displaystyle \ell <n}$ ${\displaystyle n}$ ${\displaystyle v_{n}}$ ${\displaystyle n}$ ${\displaystyle \operatorname {Vol} _{n}(v_{n})>0}$

一般に、 のとき、それらはアフィン独立である。これは、一般的なn単体が非退化であるためである。例えば、平面上の3点は一般に共線的ではない。なぜなら、それらが張る三角形は線分に退化しないからである。同様に、空間上の4点は一般に共面的ではない。なぜなら、それらが張る四面体は平面三角形に退化しないからである。 ${\displaystyle k\geq n}$

のとき、それらは必ずアフィン従属である。これは、 に収まる任意の -単体が「平坦」でなければならないことに注目すればわかる。 ${\displaystyle n>k}$ ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{k}}$

ケーリー・メンガー行列式

ケーリー・メンガー行列式は、アーサー・ケーリーとカール・メンガーにちなんで名付けられ、点の集合間の距離の行列式の行列式です。

 半距離空間にn + 1個の点があるとすると、それらのケーリー・メンガー行列式は次のように定義される。 ${\textstyle A_{0},A_{1},\ldots ,A_{n}}$

${\displaystyle \operatorname {CM} (A_{0},\cdots ,A_{n})={\begin{vmatrix}0&d_{01}^{2}&d_{02}^{2}&\cdots &d_{0n}^{2}&1\\d_{01}^{2}&0&d_{12}^{2}&\cdots &d_{1n}^{2}&1\\d_{02}^{2}&d_{12}^{2}&0&\cdots &d_{2n}^{2}&1\\\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\d_{0n}^{2}&d_{1n}^{2}&d_{2n}^{2}&\cdots &0&1\\1&1&1&\cdots &1&0\end{vmatrix}}}$

ならば、それらはにおける退化している可能性のあるn単体の頂点を構成する。 ^[6]によれば、単体の n 次元体積は次式を満たす 。 ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$ ${\displaystyle v_{n}}$ ${\displaystyle \mathbb {R} ^{k}}$ ${\displaystyle v_{n}}$

${\displaystyle \operatorname {Vol} _{n}(v_{n})^{2}={\frac {(-1)^{n+1}}{(n!)^{2}2^{n}}}\operatorname {CM} (A_{0},\ldots ,A_{n}).}$

の場合、 となり、0 単体の「0 次元体積」は 1 である、つまり、0 単体には 1 つの点があるということに注意してください。 ${\displaystyle n=0}$ ${\displaystyle \operatorname {Vol} _{0}(v_{0})=1}$

${\textstyle A_{0},A_{1},\ldots ,A_{n}}$がアフィン独立である場合、それは 、つまり である。したがって、ケーリー・メンガー行列式はアフィン独立性を計算する方法を与える。 ${\displaystyle \operatorname {Vol} _{n}(v_{n})>0}$ ${\displaystyle (-1)^{n+1}\operatorname {CM} (A_{0},\ldots ,A_{n})>0}$

ならば、点は必ずアフィン従属であるため、 となります。ケイリーの 1841 年の論文では、 の特殊なケース、つまり3 次元空間内の任意の 5 つの点は を満たす必要があることを研究しました。 ${\displaystyle k<n}$ ${\displaystyle \operatorname {CM} (A_{0},\ldots ,A_{n})=0}$ ${\displaystyle k=3,n=4}$ ${\displaystyle A_{0},\ldots ,A_{4}}$ ${\displaystyle \operatorname {CM} (A_{0},\ldots ,A_{4})=0}$

歴史

距離幾何学における最初の成果は、西暦1世紀のヘロンの公式であり、これは三角形の面積を3つの頂点間の距離から求めます。西暦7世紀のブラフマグプタの公式は、これを環状四辺形に一般化しました。西暦16世紀のタルタリアは、これを一般化し、4つの頂点間の距離から四面体の体積を求めました。

現代の距離幾何学理論は、アーサー・ケイリーとカール・メンガーによって始まった。^[7]ケイリーは1841年にケイリー行列式を発表した。^[8]これは一般的なケイリー・メンガー行列式の特殊なケースである。メンガーは1928年に、n次元ユークリッド空間 に等長的に埋め込み可能なすべての半距離空間の特徴づけ定理を証明した。^{[9] [10]} 1931年、メンガーは距離関係を用いてユークリッド幾何学の公理的扱いを与えた。^[11] ${\displaystyle \mathbb {R} ^{n}}$

レナード・ブルメンタールの著書^[12]は、大学院レベルの距離幾何学の概要を示しており、その大部分は出版時に初めて英語で扱われたものである。

メンガーの特徴定理

メンガーは半距離空間の次のような特徴づけ定理を証明した。 ^[2]

半距離空間は、次元ユークリッド空間に等長的に埋め込み可能ですが、任意の に対して には埋め込みできません。その場合、次のことが当てはまります。 ${\displaystyle (R,d)}$ ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \mathbb {R} ^{m}}$ ${\displaystyle 0\leq m<n}$

1. ${\displaystyle R}$には、 のアフィン独立な- 点部分集合と等長な- 点部分集合が含まれます。 ${\displaystyle (n+1)}$ ${\displaystyle S}$ ${\displaystyle (n+1)}$ ${\displaystyle \mathbb {R} ^{n}}$
2. の任意の 2 つの追加点を に加えて得られる任意の - 点部分集合は、の - 点部分集合と合同です。 ${\displaystyle (n+3)}$ ${\displaystyle S'}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle (n+3)}$ ${\displaystyle \mathbb {R} ^{n}}$

この定理の証明は、やや弱められた形（半距離空間ではなく距離空間の場合）で示されている。^[13]

ケーリー・メンガー行列式による特徴づけ

ブルーメタールの著書では以下の結果が証明されている。^[12]

埋め込みn実数で+1ポイント

半距離空間 が与えられ、 および が与えられたとき、 へのの等長埋め込みが によって定義され、すべての に対してが成り立ちます。 ${\displaystyle (S,d)}$ ${\displaystyle S=\{P_{0},\ldots ,P_{n}\}}$ ${\displaystyle d(P_{i},P_{j})=d_{ij}\geq 0}$ ${\displaystyle 0\leq i<j\leq n}$ ${\displaystyle (S,d)}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{n}}$ ${\displaystyle d(A_{i},A_{j})=d_{ij}}$ ${\displaystyle 0\leq i<j\leq n}$

ここでも、 に対してそのような等長埋め込みが存在するかどうかが問われます。 ${\displaystyle (S,d)}$

必要条件は簡単に分かる。すべての に対して、が によって形成されるk単体 とすると、 ${\displaystyle k=1,\ldots ,n}$ ${\displaystyle v_{k}}$ ${\textstyle A_{0},A_{1},\ldots ,A_{k}}$

${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})=(-1)^{k+1}\operatorname {CM} (A_{0},\ldots ,A_{k})=2^{k}(k!)^{k}\operatorname {Vol} _{k}(v_{k})^{2}\geq 0}$

逆もまた成り立つ。つまり、すべての に対して、 ${\displaystyle k=1,\ldots ,n}$

${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0,}$

そのような埋め込みが存在します。

さらに、このような埋め込みは における等長変換を除いて一意です。つまり、 、、で定義される任意の2つの等長変換埋め込みが与えられた場合、すべての に対してとなる（必ずしも一意ではない）等長変換 が存在します。このような は、 、つまり がアフィン独立である場合に限り一意です。 ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle A_{0},A_{1},\ldots ,A_{n}}$ ${\displaystyle A'_{0},A'_{1},\ldots ,A'_{n}}$ ${\displaystyle T:\mathbb {R} ^{n}\to \mathbb {R} ^{n}}$ ${\displaystyle T(A_{k})=A'_{k}}$ ${\displaystyle k=0,\ldots ,n}$ ${\displaystyle T}$ ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n})\neq 0}$ ${\displaystyle A_{0},A_{1},\ldots ,A_{n}}$

埋め込みn+ 2とn+3ポイント

点がにとして埋め込むことができる場合、上記の条件の他に、によって形成される -単体 が -次元の体積を持たないことも必要な条件として追加されます。つまり、 です。 ${\displaystyle n+2}$ ${\displaystyle P_{0},\ldots ,P_{n+1}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle A_{0},\ldots ,A_{n+1}}$ ${\displaystyle (n+1)}$ ${\displaystyle A_{0},A_{1},\ldots ,A_{n+1}}$ ${\displaystyle (n+1)}$ ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0}$

逆もまた成り立つ。つまり、すべての に対して、 ${\displaystyle k=1,\ldots ,n}$

${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0,}$

そして

${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0,}$

そのような埋め込みが存在します。

における点の埋め込みの場合も、必要条件と十分条件は同様です。 ${\displaystyle n+3}$ ${\displaystyle \mathbb {R} ^{n}}$

1. すべての、; ${\displaystyle k=1,\ldots ,n}$ ${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0}$
2. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0;}$
3. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+2})=0;}$
4. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1},P_{n+2})=0.}$

任意の数の点を埋め込む

このケースは一般的に十分であることが判明しました。 ${\displaystyle n+3}$

一般に、半距離空間 が与えられたとき、が存在する場合のみ、 は に等長的に埋め込まれ、すべての に対して、、任意の に対して、 ${\displaystyle (R,d)}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle P_{0},\ldots ,P_{n}\in R}$ ${\displaystyle k=1,\ldots ,n}$ ${\displaystyle (-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0}$ ${\displaystyle P_{n+1},P_{n+2}\in R}$

1. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0;}$
2. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+2})=0;}$
3. ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1},P_{n+2})=0.}$

そして、そのような埋め込みは、 における等長変換まで一意です。 ${\displaystyle \mathbb {R} ^{n}}$

さらに、 の場合、 は のいずれにも等長的に埋め込むことはできません。また、そのような埋め込みは における一意の等長性を除いて一意です。 ${\displaystyle \operatorname {CM} (P_{0},\ldots ,P_{n})\neq 0}$ ${\displaystyle \mathbb {R} ^{m},m<n}$ ${\displaystyle \mathbb {R} ^{n}}$

したがって、ケーリー・メンガー行列式は、ある有限の に対して半距離空間を に埋め込むことができるかどうかを計算する具体的な方法を提供します。また、埋め込むことができる場合は、最小の は何かを計算します。 ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle n}$ ${\displaystyle n}$

アプリケーション

距離幾何学の応用は数多くある。^[3]

GPSなどの通信ネットワークでは、いくつかのセンサーの位置（アンカーと呼ばれる）がわかっており、センサー間の距離もわかっている。問題はすべてのセンサーの位置を特定することである。^[5] 双曲航法はGPS以前の技術の1つで、信号がアンカーに到達するまでの時間に基づいて船舶の位置を特定するために距離幾何学を使用する。

化学には多くの応用があります。^{[4] [12]} NMRなどの技術は、特定の分子の原子対間の距離を測定することができ、問題はそれらの距離から分子の3次元形状を推測することです。

アプリケーション用のソフトウェア パッケージには次のようなものがあります。

• DGSOL。高分子モデリングにおける長距離幾何学問題を解決します。
• Xplor-NIH。X -PLORをベースに、NMR実験データに基づいて分子の構造を決定します。ヒューリスティック手法（シミュレーテッドアニーリングなど）と局所探索手法（共役勾配最小化など）を用いて、距離幾何学問題を解きます。
• TINKER。分子モデリングと設計。距離幾何学の問題を解くことができます。
• SNLSDPclique。センサー間の距離に基づいてセンサー ネットワーク内のセンサーの位置を特定するための MATLAB コード。

参照

• ユークリッド距離行列
• 多次元尺度法（ランダム誤差を伴って距離を測定する際に使用される統計手法）
• 計量空間
• タルタリアの公式
• 三角測量
• 三辺測量

参考文献

1. Yemini, Y. (1978). 「位置決め問題 — 中間要約の草稿」.分散センサーネットワーク会議、ピッツバーグ.
2. Liberti, Leo; Lavor, Carlile; MacUlan, Nelson; Mucherino, Antonio (2014). 「ユークリッド距離幾何学とその応用」SIAM Review . 56 : 3– 69. arXiv : 1205.0349 . doi :10.1137/120875909. S2CID  15472897.
3. Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N. (2013). 距離幾何学：理論、方法、応用.
4. Crippen, GM; Havel, TF (1988).距離幾何学と分子コンフォメーション. John Wiley & Sons.
5. Biswas, P.; Lian, T.; Wang, T.; Ye, Y. (2006). 「半正定値計画法に基づくセンサーネットワークの位置推定アルゴリズム」. ACM Transactions on Sensor Networks . 2 (2): 188– 220. doi :10.1145/1149283.1149286. S2CID  8002168.
6. “Simplex Volumes and the Cayley–Menger Determinant”. www.mathpages.com . 2019年5月16日時点のオリジナルよりアーカイブ。 2019年6月8日閲覧。
7. Liberti, Leo; Lavor, Carlile (2016). 「距離幾何学の歴史における6つの数学的宝石」. International Transactions in Operational Research . 23 (5): 897– 920. arXiv : 1502.02816 . doi :10.1111/itor.12170. ISSN  1475-3995. S2CID  17299562.
8. ケイリー、アーサー (1841). 「位置の幾何学における定理について」.ケンブリッジ数学ジャーナル. 2 : 267–271 .
9. カール、メンガー (1928-12-01)。 「Untersuchungen uber allgemeine Metrik」。Mathematische Annalen (ドイツ語)。100 (1): 75–163。土井:10.1007/BF01448840。ISSN  1432-1807。S2CID  179178149。
10. Blumenthal, LM; Gillam, BE (1943). 「n空間における点の分布」 .アメリカ数学月刊誌. 50 (3): 181. doi :10.2307/2302400. JSTOR  2302400.
11. メンガー、カール (1931). 「ユークリッド幾何学の新基礎」.アメリカ数学ジャーナル. 53 (4): 721– 745. doi :10.2307/2371222. ISSN  0002-9327. JSTOR  2371222.
12. Blumenthal, Leonard M. (1953). 『距離幾何学の理論と応用』オックスフォード大学出版局.（第2版、チェルシー：1970年）
13. Bowers, John C.; Bowers, Philip L. (2017年12月13日). 「メンガーの再解釈：ユークリッド空間への距離空間の等長的埋め込み」アメリカ数学月刊誌. 124 (7): 621. doi :10.4169/amer.math.monthly.124.7.621. S2CID  50040864.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Distance_geometry&oldid=1317939845"