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

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

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

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

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

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

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

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

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

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

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

Определения

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

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

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

Явно мы определяем полуметрическое пространство как непустое множество ${ 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 д (х, у) = д (у, х)}$.

Любое метрическое пространство 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)}$ определенное выше, изометрическое вложение в определяется точками ${ textstyle A_ {0}, A_ {1}, ldots, A_ {n} in { displaystyle mathbb {R} ^ {k}}}$, так что ${ displaystyle d (A_ {i}, A_ {j}) = d_ {ij}}$ для всех ${ Displaystyle 0 Leq я$.

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

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

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

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

Детерминанты Кэли-Менгера

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

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

${ displaystyle 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 { displaystyle mathbb {R} ^ {k}}}$, то они составляют вершины некоторого (возможно выродиться) n-симплекс ${ displaystyle { displaystyle v_ {n}}}$ в ${ displaystyle mathbb {R} ^ {k}}$. Можно показать, что^[6] n-мерный объем симплекса ${ displaystyle { displaystyle v_ {n}}}$ удовлетворяет

${ displaystyle Vol_ {n} (v_ {n}) ^ {2} = { frac {(-1) ^ {n + 1}} {(n!) ^ {2} 2 ^ {n}}} см (A_ {0}, cdots, A_ {n})}$.

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

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

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

История

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

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

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

Характеризационная теорема Менгера

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

Полуметрическое пространство ${ displaystyle (R, d)}$ изометрически вложима в ${ displaystyle n}$-мерное евклидово пространство ${ Displaystyle mathbb {R} ^ {п}}$, но не в ${ Displaystyle mathbb {R} ^ {m}}$ для любого ${ Displaystyle 0 Leq м <п}$, если и только если:

1. ${ displaystyle R}$ содержит ${ Displaystyle (п + 1)}$подмножество точек ${ displaystyle S}$ который изометричен с аффинно независимым ${ Displaystyle (п + 1)}$-точечное подмножество ${ Displaystyle mathbb {R} ^ {п}}$;
2. Любые ${ Displaystyle (п + 3)}$подмножество точек ${ displaystyle S '}$, полученный добавлением любых двух дополнительных точек ${ displaystyle R}$ к ${ displaystyle S}$, конгруэнтно ${ Displaystyle (п + 3)}$-точечное подмножество ${ Displaystyle mathbb {R} ^ {п}}$.

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

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

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

Встраивание ${ displaystyle n + 1}$ указывает в ${ Displaystyle mathbb {R} ^ {п}}$

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

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

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

${ displaystyle (-1) ^ {k + 1} CM (P_ {0}, cdots, P_ {k}) = (- 1) ^ {k + 1} CM (A_ {0}, cdots, A_ {k}) = 2 ^ {k} (k!) ^ {k} Vol_ {k} (v_ {k}) ^ {2} geq 0}$

Верно и обратное. Это если для всех ${ Displaystyle к = 1, cdots, п}$,

${ displaystyle (-1) ^ {k + 1} см (P_ {0}, cdots, P_ {k}) geq 0}$,

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

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

Встраивание ${ displaystyle n + 2}$ и ${ displaystyle n + 3}$ точки

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

Верно и обратное. Это если для всех ${ Displaystyle к = 1, cdots, п}$,

${ displaystyle (-1) ^ {k + 1} см (P_ {0}, cdots, P_ {k}) geq 0}$,

и

${ Displaystyle CM (P_ {0}, cdots, P_ {n}, P_ {n + 1}) = 0}$,

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

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

1. Для всех ${ Displaystyle к = 1, cdots, п}$, ${ displaystyle (-1) ^ {k + 1} см (P_ {0}, cdots, P_ {k}) geq 0}$;
2. ${ Displaystyle CM (P_ {0}, cdots, P_ {n}, P_ {n + 1}) = 0}$;
3. ${ Displaystyle CM (P_ {0}, cdots, P_ {n}, P_ {n + 2}) = 0}$;
4. ${ Displaystyle CM (P_ {0}, cdots, P_ {n}, P_ {n + 1}, P_ {n + 2}) = 0}$.

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

В ${ displaystyle n + 3}$ дела в целом оказывается достаточно.

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

1. ${ Displaystyle CM (P_ {0}, cdots, P_ {n}, P_ {n + 1}) = 0}$;
2. ${ Displaystyle CM (P_ {0}, cdots, P_ {n}, P_ {n + 2}) = 0}$;
3. ${ Displaystyle CM (P_ {0}, cdots, P_ {n}, P_ {n + 1}, P_ {n + 2}) = 0}$.

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

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

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

Приложения

Есть много применений дистанционной геометрии.^[3]

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

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

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

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

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

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

использованная литература