Дистанционная геометрия

Дистанционная геометрия — это раздел математики, занимающийся характеристикой и изучением множеств точек, основанных только на заданных значениях расстояний между парами точек. ^{[1] [2] [3]} Более абстрактно, это изучение полуметрических пространств и изометрических преобразований между ними. С этой точки зрения, ее можно рассматривать как предмет в рамках общей топологии . ^[4]

Исторически первым результатом в геометрии расстояний является формула Герона в 1 веке нашей эры. Современная теория началась в 19 веке с работы Артура Кэли , за которой последовали более обширные разработки в 20 веке Карла Менгера и других.

Задачи геометрии расстояний возникают всякий раз, когда необходимо определить форму конфигурации точек ( относительные положения ) на основе расстояний между ними, например, в биологии ^[4] , сенсорных сетях ^[5] , геодезии , навигации , картографии и физике .

Введение и определения

Сначала мы объясним концепции дистанционной геометрии, описав две конкретные задачи.

Задача гиперболической навигации

Первая проблема:гиперболическая навигация

Рассмотрим три наземные радиостанции 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})}$

Вторая проблема:уменьшение размеров

При анализе данных часто дается список данных, представленных в виде векторов , и нужно выяснить, лежат ли они в низкоразмерном аффинном подпространстве. Низкоразмерное представление данных имеет много преимуществ, таких как экономия места для хранения, времени вычислений и предоставление лучшего понимания данных. ${\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)}$

Любое метрическое пространство a fortiori является полуметрическим пространством. В частности, , -мерное евклидово пространство , является каноническим метрическим пространством в геометрии расстояний. ${\displaystyle \mathbb {R} ^{k}}$ ${\displaystyle k}$

Неравенство треугольника опущено в определении, поскольку мы не хотим накладывать дополнительных ограничений на расстояния, помимо простого требования, чтобы они были положительными. ${\displaystyle d_{ij}}$

На практике полуметрические пространства естественным образом возникают из неточных измерений. Например, если заданы три точки на прямой, с , неточное измерение может дать , нарушая неравенство треугольника. ${\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}$

Изометрическое вложение

Для двух полуметрических пространств, изометрическое вложение из в является отображением , которое сохраняет полуметрику, то есть для всех , . ${\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}$

Аффинная независимость

Учитывая точки , они определяются как аффинно независимые , если и только если они не могут поместиться внутри одномерного аффинного подпространства , для любого , если и только если охватываемый ими симплекс , имеет положительный -объем, то есть . ${\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 года изучался особый случай , то есть любые пять точек в трехмерном пространстве должны иметь . ${\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}$

История

Первым результатом в геометрии расстояний является формула Герона , полученная в I веке н. э., которая вычисляет площадь треугольника по расстоянию между его тремя вершинами. Формула Брахмагупты , полученная в VII веке н. э., обобщает ее на вписанные четырехугольники . Тарталья , полученный в XVI веке н. э., обобщил ее, чтобы вычислить объем тетраэдра по расстоянию между его четырьмя вершинами.

Современная теория геометрии расстояний началась с Артура Кэли и Карла Менгера . ^[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. любое -точечное подмножество , полученное добавлением любых двух дополнительных точек из к , конгруэнтно -точечному подмножеству из . ${\displaystyle (n+3)}$ ${\displaystyle S'}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle (n+3)}$ ${\displaystyle \mathbb {R} ^{n}}$

Доказательство этой теоремы в несколько ослабленном виде (для метрических пространств вместо полуметрических) приведено в ^{[13] .}

Характеристика с помощью детерминант Кэли–Менгера

В книге Блюметаля доказаны следующие результаты. ^[12]

Встраиваниен+ 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,}$

то такое вложение существует.

Далее, такое вложение уникально с точностью до изометрии в . То есть, если заданы любые два изометрических вложения, определяемые как , и , то существует (не обязательно уникальная) изометрия , такая, что для всех . Это уникально тогда и только тогда , когда , то есть аффинно независимы. ${\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}}$

Встраиваниен+ 2 ин+ 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, которая использует геометрию расстояний для определения местоположения судов на основе времени, необходимого сигналам для достижения якорей.

Существует множество приложений в химии. ^{[4] [12]} Такие методы, как ЯМР, позволяют измерять расстояния между парами атомов данной молекулы, и проблема состоит в том, чтобы вывести трехмерную форму молекулы из этих расстояний.

Некоторые программные пакеты для приложений:

• DGSOL. Решает задачи геометрии на больших расстояниях в макромолекулярном моделировании .
• Xplor-NIH. Основан на X-PLOR , для определения структуры молекул на основе данных экспериментов ЯМР. Решает проблемы геометрии расстояний с помощью эвристических методов (таких как имитация отжига ) и методов локального поиска (таких как минимизация сопряженных градиентов ).
• TINKER. Молекулярное моделирование и проектирование. Может решать проблемы геометрии расстояний.
• SNLSDPclique. Код MATLAB для определения местоположения датчиков в сенсорной сети на основе расстояний между датчиками.

Смотрите также

• Матрица евклидовых расстояний
• Многомерное шкалирование (статистический метод, используемый при измерении расстояний со случайными ошибками)
• Метрическое пространство
• Формула Тартальи
• Триангуляция
• Трилатерация

Ссылки

1. Йемини, И. (1978). «Проблема позиционирования — черновик промежуточного резюме». Конференция по распределенным сенсорным сетям, Питтсбург .
2. Liberti, Leo; Lavor, Carlile; MacUlan, Nelson; Mucherino, Antonio (2014). «Euclidean Distance Geometry and Applications». SIAM Review . 56 : 3–69. arXiv : 1205.0349 . doi : 10.1137/120875909. S2CID  15472897.
3. Мучерино, А.; Лавор, К.; Либерти, Л.; Макулан, Н. (2013). Дистанционная геометрия: теория, методы и приложения.
4. Криппен, ГМ; Хавел, ТФ (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 . Архивировано из оригинала 16 мая 2019 . Получено 2019-06-08 .
7. Либерти, Лео; Лавор, Карлайл (2016). «Шесть математических жемчужин из истории дистанционной геометрии». Международные труды по исследованию операций . 23 (5): 897–920. arXiv : 1502.02816 . doi :10.1111/itor.12170. ISSN  1475-3995. S2CID  17299562.
8. Кейли, Артур (1841). «О теореме в геометрии положения». Cambridge Mathematical Journal . 2 : 267–271.
9. Менгер, Карл (1 декабря 1928). «Untersuchungen über allgemeine Metrik». Mathematische Annalen (на немецком языке). 100 (1): 75–163. дои : 10.1007/BF01448840. ISSN  1432-1807. S2CID  179178149.
10. Блюменталь, Л. М.; Гиллам, Б. Э. (1943). «Распределение точек в n-пространстве». The American Mathematical Monthly . 50 (3): 181. doi :10.2307/2302400. JSTOR  2302400.
11. Менгер, Карл (1931). «Новое основание евклидовой геометрии». American Journal of Mathematics . 53 (4): 721–745. doi :10.2307/2371222. ISSN  0002-9327. JSTOR  2371222.
12. Блюменталь, Леонард М. (1953). Теория и приложения дистанционной геометрии . Oxford University Press.(2-е издание, Челси: 1970)
13. Боуэрс, Джон К.; Боуэрс, Филип Л. (2017-12-13). «Возвращение Менгера: изометрическое вложение метрических пространств в евклидово пространство». The American Mathematical Monthly . 124 (7): 621. doi :10.4169/amer.math.monthly.124.7.621. S2CID  50040864.