Геометрия расстояния

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

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

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

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

Концепции геометрии расстояния сначала будут объяснены путем описания двух конкретных проблем.

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

Рассмотрим три наземные радиостанции A, B, C, местоположение которых известно. Радиоприемник находится в неизвестном месте. Время, необходимое радиосигналу для прохождения от станции к приемнику, $t_{A},t_{B},t_{C}$ , неизвестны, но разница во времени, $t_{A}-t_{B}$ и $t_{A}-t_{C}$ , известны. По ним можно узнать разницу расстояний $c(t_{A}-t_{B})$ и $c(t_{A}-t_{C})$ , по которому можно определить положение приемника.

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

При анализе данных часто предоставляется список данных, представленных в виде векторов. $\mathbf {v} =(x_{1},\ldots ,x_{n})\in \mathbb {R} ^{n}$ , и нужно выяснить, лежат ли они внутри аффинного подпространства малой размерности. Низкоразмерное представление данных имеет множество преимуществ, таких как экономия места для хранения, времени вычислений и улучшение понимания данных.

Определения

Теперь формализуем некоторые определения, которые естественным образом возникают при рассмотрении наших задач.

Полуметрическое пространство

Учитывая список пунктов на $R=\{P_{0},\ldots ,P_{n}\}$ , $n\geq 0$ , мы можем произвольно указать расстояния между парами точек списком $d_{ij}>0$ , $0\leq i<j\leq n$ . Это определяет полуметрическое пространство : метрическое пространство без неравенства треугольника .

Явно мы определяем полуметрическое пространство как непустое множество $R$ оснащен полуметрическим $d:R\times R\to [0,\infty )$ такой, что для всех $x,y\in R$ ,

Позитивность: $d(x,y)=0$ тогда и только тогда, когда $x=y$ .
Симметрия: $d(x,y)=d(y,x)$ .

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

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

На практике полуметрические пространства естественным образом возникают в результате неточных измерений. Например, учитывая три точки $A,B,C$ на линии, с $d_{AB}=1,d_{BC}=1,d_{AC}=2$ , неточное измерение может дать $d_{AB}=0.99,d_{BC}=0.98,d_{AC}=2.00$ , нарушая неравенство треугольника.

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

Учитывая два полуметрических пространства, $(R,d),(R',d')$ , изометрическое вложение из $R$ к $R'$ это карта $f:R\to R'$ сохраняющий полуметрику, т. е. для всех $x,y\in R$ , $d(x,y)=d'(f(x),f(y))$ .

Например, учитывая конечное полуметрическое пространство $(R,d)$ определенное выше, изометрическое вложение из $R$ к $\mathbb {R} ^{k}$ определяется точками ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$ , такой, что $d(A_{i},A_{j})=d_{ij}$ для всех $0\leq i<j\leq n$ .

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

Учитывая баллы ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$ они определяются как аффинно независимые , если они не могут поместиться внутри одного $l$ -мерное аффинное подпространство $\mathbb {R} ^{k}$ , для любого $\ell <n$ , если $n$ - симплекс они охватывают, $v_{n}$ , имеет положительный $n$ -объем, то есть $\operatorname {Vol} _{n}(v_{n})>0$ .

В общем, когда $k\geq n$ , они аффинно независимы, поскольку общий n -симплекс невырожден. Например, 3 точки на плоскости вообще не лежат на одной прямой, потому что треугольник, который они охватывают, не вырождается в отрезок. Точно так же 4 точки в пространстве, как правило, не являются компланарными, поскольку охватываемый ими тетраэдр не вырождается в плоский треугольник.

Когда $n>k$ , они должны быть аффинно зависимы. В этом можно убедиться, заметив, что любое $n$ -симплекс, который может поместиться внутри $\mathbb {R} ^{k}$ должен быть «плоским».

Определители Кэли – Менгера

Определители Кэли-Менгера, названные в честь Артура Кэли и Карла Менгера, являются определителями матриц расстояний между наборами точек.

Позволять ${\textstyle A_{0},A_{1},\ldots ,A_{n}}$ если n + 1 точка в полуметрическом пространстве, их определитель Кэли – Менгера определяется формулой

\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}}

Если ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{k}}$ , то они составляют вершины возможно вырожденного n -симплекса $v_{n}$ в $\mathbb {R} ^{k}$ . Можно показать, что ^[6] -мерный объем n симплекса $v_{n}$ удовлетворяет

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

Обратите внимание, что для случая $n=0$ , у нас есть $\operatorname {Vol} _{0}(v_{0})=1$ , что означает, что «0-мерный объем» 0-симплекса равен 1, то есть в 0-симплексе есть 1 точка.

${\textstyle A_{0},A_{1},\ldots ,A_{n}}$ аффинно независимы тогда и только тогда, когда $\operatorname {Vol} _{n}(v_{n})>0$ , то есть, $(-1)^{n+1}\operatorname {CM} (A_{0},\ldots ,A_{n})>0$ . Таким образом, определители Кэли – Менгера дают вычислительный способ доказать аффинную независимость.

Если $k<n$ , то точки должны быть аффинно зависимы, таким образом $\operatorname {CM} (A_{0},\ldots ,A_{n})=0$ . В статье Кэли 1841 года изучался особый случай $k=3,n=4$ , то есть любые пять точек $A_{0},\ldots ,A_{4}$ в трехмерном пространстве должны иметь $\operatorname {CM} (A_{0},\ldots ,A_{4})=0$ .

История

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

Современная теория дистанционной геометрии началась с Артура Кэли и Карла Менгера . ^[7] Кэли опубликовал определитель Кэли в 1841 году. ^[8] что является частным случаем общего определителя Кэли – Менгера. Менгер доказал в 1928 году характеристическую теорему всех полуметрических пространств, изометрически вложимых в n -мерное евклидово пространство. $\mathbb {R} ^{n}$ . ^[9]^[10] В 1931 году Менгер использовал отношения расстояний, чтобы дать аксиоматическую трактовку евклидовой геометрии. ^[11]

Леонарда Блюменталя Книга ^[12] дает общий обзор дистанционной геометрии для выпускников, большая часть которого впервые рассматривается на английском языке, когда она была опубликована.

Теорема Менгера о характеризации

Менгер доказал следующую характеристическую теорему полуметрических пространств: ^[2]

Полуметрическое пространство $(R,d)$ изометрически вложима в $n$ -мерное евклидово пространство $\mathbb {R} ^{n}$ , но не в $\mathbb {R} ^{m}$ для любого $0\leq m<n$ , тогда и только тогда, когда:
$R$ содержит $(n+1)$ -точечное подмножество $S$ изометрический с аффинно независимым $(n+1)$ -точечное подмножество $\mathbb {R} ^{n}$ ;
любой $(n+3)$ -точечное подмножество $S'$ , полученный сложением любых двух дополнительных точек $R$ к $S$ , соответствует $(n+3)$ -точечное подмножество $\mathbb {R} ^{n}$ .

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

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

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

Вложение n + 1 точек в действительные числа

Учитывая полуметрическое пространство $(S,d)$ , с $S=\{P_{0},\ldots ,P_{n}\}$ , и $d(P_{i},P_{j})=d_{ij}\geq 0$ , $0\leq i<j\leq n$ , изометрическое вложение $(S,d)$ в $\mathbb {R} ^{n}$ определяется ${\textstyle A_{0},A_{1},\ldots ,A_{n}\in \mathbb {R} ^{n}}$ , такой, что $d(A_{i},A_{j})=d_{ij}$ для всех $0\leq i<j\leq n$ .

И снова возникает вопрос, существует ли такое изометрическое вложение для $(S,d)$ .

Необходимое условие легко увидеть: для всех $k=1,\ldots ,n$ , позволять $v_{k}$ — k -симплекс, образованный ${\textstyle A_{0},A_{1},\ldots ,A_{k}}$ , затем

(-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

Обратное также справедливо. То есть, если для всех $k=1,\ldots ,n$ ,

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

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

Далее, такое вложение единственно с точностью до изометрии в $\mathbb {R} ^{n}$ . То есть, учитывая любые два изометрических вложения, определяемые формулой $A_{0},A_{1},\ldots ,A_{n}$ , и $A'_{0},A'_{1},\ldots ,A'_{n}$ , существует (не обязательно единственная) изометрия $T:\mathbb {R} ^{n}\to \mathbb {R} ^{n}$ , такой, что $T(A_{k})=A'_{k}$ для всех $k=0,\ldots ,n$ . Такой $T$ уникально тогда и только тогда, когда $\operatorname {CM} (P_{0},\ldots ,P_{n})\neq 0$ , то есть, $A_{0},A_{1},\ldots ,A_{n}$ аффинно независимы.

Вложение n + 2 и n + 3 точек

Если $n+2$ очки $P_{0},\ldots ,P_{n+1}$ может быть встроен в $\mathbb {R} ^{n}$ как $A_{0},\ldots ,A_{n+1}$ , то кроме условий, указанных выше, дополнительным необходимым условием является то, что $(n+1)$ -симплекс, образованный $A_{0},A_{1},\ldots ,A_{n+1}$ , должно быть нет $(n+1)$ -мерный объем. То есть, $\operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0$ .

Обратное также справедливо. То есть, если для всех $k=1,\ldots ,n$ ,

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

и

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

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

Для встраивания $n+3$ указывает на $\mathbb {R} ^{n}$ , необходимые и достаточные условия аналогичны:

Для всех $k=1,\ldots ,n$ , $(-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0$ ;
$\operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1})=0;$
$\operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+2})=0;$
$\operatorname {CM} (P_{0},\ldots ,P_{n},P_{n+1},P_{n+2})=0.$

Вложение произвольного количества точек

The $n+3$ случае оказывается, вообще говоря, достаточным.

В общем случае, учитывая полуметрическое пространство $(R,d)$ , его можно изометрически вложить в $\mathbb {R} ^{n}$ тогда и только тогда, когда существует $P_{0},\ldots ,P_{n}\in R$ , такой, что для всех $k=1,\ldots ,n$ , $(-1)^{k+1}\operatorname {CM} (P_{0},\ldots ,P_{k})\geq 0$ , и для любого $P_{n+1},P_{n+2}\in R$ ,

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

И такое вложение единственно с точностью до изометрии в $\mathbb {R} ^{n}$ .

Далее, если $\operatorname {CM} (P_{0},\ldots ,P_{n})\neq 0$ , то его нельзя изометрически вложить ни в какую $\mathbb {R} ^{m},m<n$ . И такое вложение единственно с точностью до уникальной изометрии в $\mathbb {R} ^{n}$ .

Таким образом, определители Кэли – Менгера дают конкретный способ вычислить, можно ли вложить полуметрическое пространство в $\mathbb {R} ^{n}$ , для некоторого конечного $n$ и если да, то какова минимальная $n$ .

Приложения

Существует множество приложений дистанционной геометрии. ^[3]

В телекоммуникационных сетях, таких как GPS , известны положения некоторых датчиков (которые называются якорями), а также известны некоторые расстояния между датчиками: проблема состоит в том, чтобы определить положения всех датчиков. ^[5] Гиперболическая навигация — это одна из технологий, предшествующих GPS, которая использует геометрию расстояния для определения местоположения судов на основе времени, необходимого сигналам для достижения якоря.

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

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

ДГСОЛ . Решает проблемы геометрии на больших расстояниях при моделировании макромолекул .
Xplor-NIH . На основе X-PLOR , для определения структуры молекул на основе данных экспериментов ЯМР. Он решает проблемы геометрии расстояния с помощью эвристических методов (таких как имитация отжига ) и методов локального поиска (таких как минимизация сопряженного градиента ).
ТИНКЕР . Молекулярное моделирование и дизайн. Это может решить проблемы геометрии расстояния.
SNLSDPclique . Код MATLAB для поиска датчиков в сенсорной сети на основе расстояний между датчиками.

См. также

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

Ссылки

^ Йемини, Ю. (1978). «Проблема позиционирования — проект промежуточного резюме». Конференция по распределенным сенсорным сетям, Питтсбург .
^ Jump up to: ^а ^б Либерти, Лео; Лавор, Карлайл; Макулан, Нельсон; Мучерино, Антонио (2014). «Евклидова дистанционная геометрия и приложения». Обзор СИАМ . 56 : 3–69. arXiv : 1205.0349 . дои : 10.1137/120875909 . S2CID 15472897 .
^ Jump up to: ^а ^б Мучерино, А.; Лавор, К.; Либерти, Л.; Макулан, Н. (2013). Дистанционная геометрия: теория, методы и приложения .
^ Jump up to: ^а ^б ^с Криппен, генеральный менеджер; Гавел, Т.Ф. (1988). Дистанционная геометрия и молекулярная конформация . Джон Уайли и сыновья.
^ Jump up to: ^а ^б Бисвас, П.; Лиан, Т.; Ван, Т.; Йе, Ю. (2006). «Алгоритмы локализации сенсорных сетей на основе полуопределенного программирования». Транзакции ACM в сенсорных сетях . 2 (2): 188–220. дои : 10.1145/1149283.1149286 . S2CID 8002168 .
^ «Симплексные объемы и определитель Кэли – Менгера» . www.mathpages.com . Архивировано из оригинала 16 мая 2019 года . Проверено 8 июня 2019 г.
^ Либерти, Лео; Лавор, Карлайл (2016). «Шесть математических жемчужин из истории дистанционной геометрии». Международные сделки в области операционных исследований . 23 (5): 897–920. arXiv : 1502.02816 . дои : 10.1111/itor.12170 . ISSN 1475-3995 . S2CID 17299562 .
^ Кэли, Артур (1841). «Об одной теореме геометрии положения». Кембриджский математический журнал . 2 : 267–271.
^ Менгер, Карл (1 декабря 1928). «Исследования по общим метрикам». Математические анналы (на немецком языке). 100 (1): 75–163. дои : 10.1007/BF01448840 . ISSN 1432-1807 . S2CID 179178149 .
^ Блюменталь, LM; Гиллам, Б.Э. (1943). «Распределение точек в n -пространстве» . Американский математический ежемесячник . 50 (3): 181. дои : 10.2307/2302400 . JSTOR 2302400 .
^ Менгер, Карл (1931). «Новое основание евклидовой геометрии». Американский журнал математики . 53 (4): 721–745. дои : 10.2307/2371222 . ISSN 0002-9327 . JSTOR 2371222 .
^ Jump up to: ^а ^б ^с Блюменталь, Леонард М. (1953). Теория и приложения дистанционной геометрии . Издательство Оксфордского университета. ( 2-е издание , Челси: 1970 г.)
^ Бауэрс, Джон К.; Бауэрс, Филип Л. (13 декабря 2017 г.). «Редукс Менгера: изометрическое вложение метрических пространств в евклидово пространство». Американский математический ежемесячник . 124 (7): 621. doi : 10.4169/amer.math.monthly.124.7.621 . S2CID 50040864 .

[positioning-1] Йемини, Ю. (1978). «Проблема позиционирования — проект промежуточного резюме». Конференция по распределенным сенсорным сетям, Питтсбург .

[siam-2] Jump up to: ^а ^б Либерти, Лео; Лавор, Карлайл; Макулан, Нельсон; Мучерино, Антонио (2014). «Евклидова дистанционная геометрия и приложения». Обзор СИАМ . 56 : 3–69. arXiv : 1205.0349 . дои : 10.1137/120875909 . S2CID 15472897 .

[DGAbook-3] Jump up to: ^а ^б Мучерино, А.; Лавор, К.; Либерти, Л.; Макулан, Н. (2013). Дистанционная геометрия: теория, методы и приложения .

[crippen-4] Jump up to: ^а ^б ^с Криппен, генеральный менеджер; Гавел, Т.Ф. (1988). Дистанционная геометрия и молекулярная конформация . Джон Уайли и сыновья.

[sensors-5] Jump up to: ^а ^б Бисвас, П.; Лиан, Т.; Ван, Т.; Йе, Ю. (2006). «Алгоритмы локализации сенсорных сетей на основе полуопределенного программирования». Транзакции ACM в сенсорных сетях . 2 (2): 188–220. дои : 10.1145/1149283.1149286 . S2CID 8002168 .

[6] «Симплексные объемы и определитель Кэли – Менгера» . www.mathpages.com . Архивировано из оригинала 16 мая 2019 года . Проверено 8 июня 2019 г.

[7] Либерти, Лео; Лавор, Карлайл (2016). «Шесть математических жемчужин из истории дистанционной геометрии». Международные сделки в области операционных исследований . 23 (5): 897–920. arXiv : 1502.02816 . дои : 10.1111/itor.12170 . ISSN 1475-3995 . S2CID 17299562 .

[8] Кэли, Артур (1841). «Об одной теореме геометрии положения». Кембриджский математический журнал . 2 : 267–271.

[9] Менгер, Карл (1 декабря 1928). «Исследования по общим метрикам». Математические анналы (на немецком языке). 100 (1): 75–163. дои : 10.1007/BF01448840 . ISSN 1432-1807 . S2CID 179178149 .

[:0-10] Блюменталь, LM; Гиллам, Б.Э. (1943). «Распределение точек в n -пространстве» . Американский математический ежемесячник . 50 (3): 181. дои : 10.2307/2302400 . JSTOR 2302400 .

[11] Менгер, Карл (1931). «Новое основание евклидовой геометрии». Американский журнал математики . 53 (4): 721–745. дои : 10.2307/2371222 . ISSN 0002-9327 . JSTOR 2371222 .

[blumenthal-12] Jump up to: ^а ^б ^с Блюменталь, Леонард М. (1953). Теория и приложения дистанционной геометрии . Издательство Оксфордского университета. ( 2-е издание , Челси: 1970 г.)

[13] Бауэрс, Джон К.; Бауэрс, Филип Л. (13 декабря 2017 г.). «Редукс Менгера: изометрическое вложение метрических пространств в евклидово пространство». Американский математический ежемесячник . 124 (7): 621. doi : 10.4169/amer.math.monthly.124.7.621 . S2CID 50040864 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]