Узкий промежуток - Tight span

Если набор точек на плоскости, с Манхэттенская метрика, имеет связанный ортогональная выпуклая оболочка, то эта оболочка совпадает с узким промежутком точек.

В метрическая геометрия, то метрический конверт или тесный промежуток из метрическое пространство M является инъективное метрическое пространство в котором M может быть встроен. В некотором смысле он состоит из всех точек «между» точками M, аналогично выпуклый корпус точки, установленной в Евклидово пространство. Узкий промежуток также иногда называют конверт для инъекций или гипервыпуклая оболочка из M. Его также называли инъективная оболочка, но не следует путать с инъективная оболочка из модуль в алгебра, концепт с аналогичным описанием относительно категория из р-модули, а не метрические пространства.

Тесный промежуток был впервые описан Исбелл (1964), и он был изучен и применен Гольштынский в 1960-е гг. Позже он был независимо открыт заново Платье (1984) и Хробак и Лармор (1994); видеть Чепой (1997) для этой истории. Герметичный пролет - одна из центральных конструкций Т-теория.

Определение

Тесную оболочку конечного метрического пространства можно определить следующим образом. Позволять (Икс,d) - метрическое пространство с Икс конечно, и пусть Т(Икс) - набор функций ж из Икс к р такой, что

Для любого Икс, у в Икс, ж(Икс) + ж(у) ≥ d(Икс,у), и
Для каждого Икс в Икс, Существует у в Икс такой, что ж(Икс) + ж(у) = d(Икс,у).

В частности (принимая Икс = у в свойстве 1 выше) ж(Икс) ≥ 0 для всех Икс. Один из способов интерпретации первого требования выше заключается в том, что ж определяет набор возможных расстояний от некоторой новой точки до точек в Икс это должно удовлетворить неравенство треугольника вместе с расстояниями в (Икс,d). Второе требование гласит, что ни одно из этих расстояний не может быть уменьшено без нарушения неравенства треугольника.

Учитывая две функции ж и грамм в Т(Икс), определим δ (ж,грамм) = макс |ж(Икс)-грамм(Икс) |; если мы рассмотрим Т(Икс) как подмножество векторного пространства р^|Икс| тогда это обычный L_∞ расстояние между векторами. Плотный промежуток Икс - метрическое пространство (Т(Икс), δ). Существует изометрическое вложение из Икс в его плотный промежуток, заданный отображением любого Икс в функцию ж_Икс(у) = d(Икс,у). Несложно расширить определение δ, используя неравенство треугольника для Икс чтобы показать, что расстояние между любыми двумя точками Икс равно расстоянию между соответствующими точками в узком пролете.

Приведенное выше определение включает в себя ограниченный диапазон набора п указывает в пространство измерения п. Однако, Девелин (2006) показал, что при подходящем предположении об общем положении метрики это определение приводит к пространству с размерностью между п/ 3 и п/2. Девелин и Штурмфельс (2004) попытался предоставить альтернативное определение узкого промежутка конечного метрического пространства, как тропическая выпуклая оболочка векторов расстояний от каждой точки до другой точки в пространстве. Однако позже в том же году они признали в Erratum Девелин и Штурмфельс (2004a) что, хотя тропическая выпуклая оболочка всегда содержит тесный пролет, она может не совпадать с ней.

Для общих (конечных и бесконечных) метрических пространств узкая область может быть определена с использованием модифицированной версии свойства 2 из определения выше, в котором указано, что inf ж(Икс) + ж(у) - d(Икс,у) = 0.^[1] Альтернативное определение, основанное на понятии метрическое пространство, направленное на его подпространство был описан Гольштынский (1968), который доказал, что инъективная оболочка банахова пространства в категории банаховых пространств совпадает (забыв о линейной структуре) с плотной оболочкой. Эта теорема позволяет свести некоторые задачи с произвольных банаховых пространств к банаховым пространствам вида C (X), где X - компактное пространство.

пример

На рисунке показан набор Икс из 16 точек в плоскости; чтобы сформировать конечное метрическое пространство из этих точек, мы используем Манхэттенское расстояние (L₁ метрическая).^[2] Синяя область, показанная на рисунке, - это ортогональная выпуклая оболочка, множество точек z такой, что каждый из четырех закрытых квадрантов с z поскольку вершина содержит точку Икс. Любая такая точка z соответствует точке узкого промежутка: функция ж(Икс) соответствующий точке z является ж(Икс) = d(z,Икс). Функция такого вида удовлетворяет свойству 1 узкой оболочки для любого z в манхэттен-метрической плоскости неравенством треугольника для манхэттенской метрики. Чтобы показать свойство 2 узкого пролета, рассмотрим некоторую точку Икс в Икс; мы должны найти у в Икс такой, что ж(Икс)+ж(у)=d(Икс,у). Но если Икс находится в одном из четырех квадрантов, имеющих z как вершина, у можно принять за любую точку в противоположном квадранте, поэтому свойство 2 также выполняется. Наоборот, можно показать, что каждая точка узкого промежутка таким образом соответствует точке в ортогональной выпуклой оболочке этих точек. Однако для наборов точек с метрикой Манхэттена в более высоких измерениях и для плоских наборов точек с несвязанными ортогональными оболочками плотный промежуток отличается от ортогональной выпуклой оболочки.

Приложения

Платье, Huber & Moulton (2001) описать приложения узкого промежутка в реконструкция эволюционных деревьев из биологических данных.
Плотность играет роль в нескольких онлайн-алгоритмы для Проблема с K-сервером.^[3]
Штурмфельс и Ю (2004) использует ограниченный диапазон для классификации метрических пространств по шести точкам.
Чепой (1997) использует ограниченный диапазон для подтверждения результатов об упаковке сократить показатели в более общие конечные метрические пространства.

Примечания

^ См. Например Платье, Huber & Moulton (2001).
^ В двух измерениях манхэттенское расстояние изометрично после вращения и масштабирования до L_∞ расстояние, поэтому с этой метрикой плоскость инъективна, но эта эквивалентность между L₁ и я_∞ не выполняется в более высоких измерениях.
^ Хробак и Лармор (1994).

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

Куратовский вложение, вложение любого метрического пространства в Банахово пространство определяется аналогично узкому промежутку

внешняя ссылка

Джозвиг, Майкл, Узкие пролеты.

[1] См. Например Платье, Huber & Moulton (2001).

[2] В двух измерениях манхэттенское расстояние изометрично после вращения и масштабирования до L_∞ расстояние, поэтому с этой метрикой плоскость инъективна, но эта эквивалентность между L₁ и я_∞ не выполняется в более высоких измерениях.

[3] Хробак и Лармор (1994).

[1]

[2]

[3]