В метрической геометрии , то метрика огибающий или жесткая оболочка из метрического пространства М является инъективным метрическим пространством , в котором М могут быть вложены. В некотором смысле он состоит из всех точек «между» точками M , аналогично выпуклой оболочке множества точек в евклидовом пространстве . Плотно оболочка также иногда известна как инъективного конверт или hyperconvex корпуса из М . Он также называется инъективный корпусом , но не следует путать с инъективной оболочкой из амодуль в алгебре , понятие с подобным описанием по отношению к категории из R - модулей , а не метрических пространств.
Плотный промежуток был впервые описан Исбеллом (1964) , а в 1960-х годах он был изучен и применен Гольштынским . Позже он был независимо заново открыт Дрессом ( 1984) и Хробаком и Лармором (1994) ; эту историю см. Chepoi (1997) . Узкий промежуток - одно из центральных построений Т-теории .
Определение
Тесную оболочку конечного метрического пространства можно определить следующим образом. Пусть ( X , d ) - метрическое пространство с конечным X , и пусть T ( X ) - множество функций f из X в R таких, что
- Для любых x , y в X , f ( x ) + f ( y ) ≥ d ( x , y ) и
- Для каждого x в X существует y в X такое, что f ( x ) + f ( y ) = d ( x , y ).
В частности (взяв x = y в свойстве 1 выше) f ( x ) ≥ 0 для всех x . Один из способов интерпретации первого требования выше состоит в том, что f определяет набор возможных расстояний от некоторой новой точки до точек в X, которые должны удовлетворять неравенству треугольника вместе с расстояниями в ( X , d ). Второе требование гласит, что ни одно из этих расстояний не может быть уменьшено без нарушения неравенства треугольника.
Для двух функций f и g из T ( X ) положим δ ( f , g ) = max | f ( x ) - g ( x ) |; если мы рассматриваем T ( X ) как подмножество векторного пространства R | X | то это обычное расстояние L ∞ между векторами. Тесная оболочка X - это метрическое пространство ( T ( X ), δ). Существует изометрическое вложение из X в его плотный промежуток, учитывая путем отображения любого х в функцию е х ( у ) = д ( х , у ). Несложно расширить определение δ, используя неравенство треугольника для X, чтобы показать, что расстояние между любыми двумя точками X равно расстоянию между соответствующими точками в узком промежутке.
Приведенное выше определение включает узкую область набора из n точек в пространство размерности n . Однако Девелин (2006) показал, что при подходящем предположении об общем положении метрики это определение приводит к пространству с размерностью от n / 3 до n / 2. Девелин и Штурмфельс (2004) попытались дать альтернативное определение узкого промежутка конечного метрического пространства как тропической выпуклой оболочки векторов расстояний от каждой точки до каждой другой точки в пространстве. Однако позже в том же году они признали в Erratum Develin & Sturmfels (2004a), что, хотя тропическая выпуклая оболочка всегда содержит узкий пролет, он может не совпадать с ним.
Для общих (конечных и бесконечных) метрических пространств узкая область может быть определена с использованием модифицированной версии свойства 2 в приведенном выше определении, в котором говорится, что inf f ( x ) + f ( y ) - d ( x , y ) = 0. [ 1] Альтернативное определение, основанное на понятии метрического пространства, нацеленного на его подпространство, было описано Холштынским (1968) , который доказал, что инъективная оболочка банахова пространства в категории банаховых пространств совпадает (забывая о линейной структуре ) с плотным пролетом. Эта теорема позволяет свести некоторые задачи с произвольных банаховых пространств к банаховым пространствам вида C (X), где X - компактное пространство.
Пример
На рисунке показан набор X из 16 точек на плоскости; чтобы сформировать конечное метрическое пространство из этих точек, мы используем манхэттенское расстояние ( метрика L 1 ). [2] синяя область показаны на рисунке является ортогональной выпуклой оболочкой , множество точек г таким образом, что каждый из четырех квадрантов с закрытых г в вершине содержит точку X . Любая такая точка z соответствует точке узкого промежутка: функция f ( x ), соответствующая точке z, есть f ( x ) = d ( z , x ). Функция этой формы удовлетворяет свойству 1 узкой оболочки для любого z в манхэттен-метрической плоскости согласно неравенству треугольника для манхэттенской метрики. Чтобы показать свойство 2 узкого промежутка, рассмотрим некоторую точку x в X ; мы должны найти y в X такое, что f ( x ) + f ( y ) = d ( x , y ). Но если x находится в одном из четырех квадрантов с z в качестве вершины, y можно принять как любую точку в противоположном квадранте, так что свойство 2 также выполняется. Наоборот, можно показать, что каждая точка узкого промежутка таким образом соответствует точке в ортогональной выпуклой оболочке этих точек. Однако для наборов точек с метрикой Манхэттена в более высоких измерениях и для плоских наборов точек с несвязанными ортогональными оболочками плотный промежуток отличается от ортогональной выпуклой оболочки.
Приложения
- Дресс, Хубер и Моултон (2001) описывают применение ограниченного промежутка времени при реконструкции эволюционных деревьев на основе биологических данных.
- Тесная пролет служит роль в нескольких онлайн - алгоритмов для задачи K-сервера . [3]
- Sturmfels & Yu (2004) использует ограниченный диапазон для классификации метрических пространств по шести точкам.
- Chepoi (1997) использует ограниченный диапазон, чтобы доказать результаты об упаковке разрезанных метрик в более общие конечные метрические пространства.
Заметки
- ^ См., Например, Dress, Huber & Moulton (2001) .
- ^ В двух измерениях манхэттенское расстояние изометрично после вращения и масштабирования до расстояния L ∞ , поэтому с этой метрикой плоскость сама инъективна, но эта эквивалентность между L 1 и L ∞ не выполняется в более высоких измерениях.
- ^ Чробак & Лармор (1994) .
Рекомендации
- Чепа, Виктор (1997), "А Т Х подход к некоторым результатам по порезам и метрикам", Advances в области прикладной математики , 19 (4): 453-470, DOI : 10,1006 / aama.1997.0549.
- Хробак, Марек; Лармор, Лоуренс Л. (1994), «Щедрость помогает или 11-конкурентный алгоритм для трех серверов», Journal of Algorithms , 16 (2): 234–263, doi : 10.1006 / jagm.1994.1011.
- Девелин, Майк (2006), «Размеры узких пролетов», Annals of Combinatorics , 10 (1): 53–61, arXiv : math.CO/0407317 , doi : 10.1007 / s00026-006-0273-y.
- Девелин, Майк; Штурмфельс, Бернд (2004), «Тропическая выпуклость» (PDF) , Documenta Mathematica , 9 : 1–27.
- Девелин, Майк; Sturmfels, Bernd (2004a), "Erratum for" Tropical Convexity " " (PDF) , Documenta Mathematica , 9 : 205–206.
- Платье, Андреас WM (1984), "Дерева, плотные расширения метрических пространств, а когомологическая размерность некоторых групп", достижения в области математики , 53 (3): 321-402, DOI : 10.1016 / 0001-8708 (84) 90029 -ИКС.
- Платье, Андреас WM; Huber, KT; Моултон, В. (2001), «Метрические пространства в чистой и прикладной математике» (PDF) , Documenta Mathematica (Proceedings Quadratic Forms LSU): 121–139.
- Holsztyński, Włodzimierz (1968), "Линеаризация изометрических вложений банаховых пространств. Метрические оболочки.", Bull. Акад. Полон. Sci. , 16 : 189–193.
- Исбелл, Дж. Р. (1964), "Шесть теорем об инъективных метрических пространствах", Комментарий. Математика. Helv. , 39 : 65-76, DOI : 10.1007 / BF02566944 CS1 maint: обескураженный параметр ( ссылка ).
- Штурмфельс, Бернд ; Ю, Жозефина (2004), «Классификация шеститочечных метрик» , Электронный журнал комбинаторики , 11 : R44, arXiv : math.MG/0403147 , Bibcode : 2004math ...... 3147S.
Смотрите также
- Вложение Куратовского , вложение любого метрического пространства в банахово пространство, определяемое аналогично узкой оболочке
Внешние ссылки
- Джозвиг, Майкл, Узкие промежутки.