Коэффициент растяжения
-
Определение коэффициента растяжения
- Коэффициент растяжения вложения измеряет искажение расстояний.
- Отображение f сохраняет или уменьшает расстояния между точками.
-
Искажение расстояний
- Пара точек в S имеет внутреннее и внешнее расстояния в T.
- Отношение внешнего к внутреннему расстоянию является коэффициентом растяжения.
- Максимальный коэффициент растяжения всего отображения определяет искажение.
-
Применение в теории геометрических гаечных ключей
- Вложение используется для аппроксимации евклидовых расстояний.
- Вложение S в T может быть представлено как метрика на графе.
- Веса ребер графа должны соответствовать евклидовым расстояниям для минимизации коэффициента растяжения.
-
Лемма Джонсона-Линденштраусса
- Конечное множество точек в евклидовом пространстве можно вложить с искажением 1 + ε.
- Методы построения вложений с низким искажением важны в теории аппроксимационных алгоритмов.
-
Гипотеза GNRS
- Основная проблема в теории — характеризация семейств графов с ограниченной протяженностью в ℓ1-пространстве.
-
Исследование деформации узлов
- Деформация узла — это минимальный коэффициент растяжения вложения узла в евклидовом пространстве.
- Исследователь Джон Пардон получил премию за решение проблемы искажения торовых узлов.
-
Монотонность коэффициента растяжения
- Хьюскен доказал, что коэффициент растяжения простой замкнутой гладкой кривой монотонно уменьшается.
- Исключение составляют случаи, когда кривая является кругом.
-
Теорема Гейджа-Гамильтона-Грейсона
- Доказательство теоремы о сохранении простоты и плавности простой замкнутой гладкой кривой основано на монотонности коэффициента растяжения.
Полный текст статьи: