Русская Википедия:Расстояние Фреше
Расстояние Фреше — это мера сходства кривых, принимающая во внимание число и порядок точек вдоль кривых. Расстояние названо по имени французского математика Мориса Фреше.
Интуитивное определение
Представим себе собаку, прогуливающуюся вдоль одной кривой, которую держит на поводке владелец собаки, идущий вдоль другой кривой. Оба проходят от начальной точки до конечной, меняя скорость, но не возвращаясь. Расстояние Фреше между этими двумя кривыми — это длина самого короткого поводка, с которым можно пройти кривые. Не самый короткий поводок, при котором можно пройти все пути, а самый короткий, при котором можно пройти путь.
Определение симметрично относительно двух кривых — вы можете думать, что собака выгуливает хозяина.
Формальное определение
Пусть <math>S</math> — метрическое пространство. Кривая <math>A</math> в пространстве <math>S</math> — это непрерывное отображение единичного отрезка в <math>S</math>, т.е. <math>A : [0,1] \rightarrow S</math>. Репараметризация <math>\alpha</math> отрезка <math>[0,1]</math> — это непрерывная неубывающая сюръекция <math>\alpha: [0,1] \rightarrow [0,1]</math>.
Пусть <math>A</math> и <math>B</math> — две кривые в <math>S</math>. Тогда расстояние Фреше между <math>A</math> и <math>B</math> определяется как точная нижняя граница по всем репараметризациям <math>\alpha</math> и <math>\beta</math> отрезка <math>[0,1]</math> по всем максимумам <math>t \in [0,1]</math> расстояний в <math>S</math> между <math>A(\alpha(t))</math> и <math>B(\beta(t))</math>. В математических обозначениях расстояние Фреше <math>F(A,B)</math> равно
<math>F(A,B) = \inf_{\alpha, \beta}\,\,\max_{t \in [0,1]} \,\, \Bigg \{d \Big ( A(\alpha(t)), \, B(\beta(t)) \Big ) \Bigg \}</math>,
где <math>d</math> — функция расстояния пространства <math>S</math>.
Неформально, мы можем считать параметр <math>t</math> «временем». Тогда <math>A(\alpha(t))</math> является положением собаки, а <math>B(\beta(t))</math> — положением владельца собаки по времени <math>t</math> (или наоборот). Длина поводка между ними в момент времени <math>t</math> равна расстоянию между <math>A(\alpha(t))</math> и <math>B(\beta(t))</math>. Взятие инфимума по всем возможным репараметризациям отрезка <math>[0,1]</math> соответствует выбору прогулки вдоль кривых, при которой максимальная длина поводка минимизируется. Ограничение, что <math>\alpha</math> и <math>\beta</math> не убывают, означает, что ни собака, ни её владелец не могут повернуть назад.
Метрика Фреше принимает во внимание течение двух кривых, поскольку пары точек, расстояние между которыми определяет расстояние Фреше, «пробегают» вдоль кривых. Это делает расстояние Фреше лучшей мерой похожести кривых по сравнению с метрикой Хаусдорфа для произвольного множества точек. Две кривые могут иметь маленькое хаусдорфово расстояние, но большое расстояние Фреше.
Расстояние Фреше и его вариации находят применение в некоторых задачах, от морфингаШаблон:Sfn и распознавания рукописного вводаШаблон:Sfn до расположения протеиновых структурШаблон:Sfn. Альт и ГодауШаблон:Sfn первыми описали алгоритм полиномиального времени для вычисления расстояния Фреше между двумя ломаными в евклидовом пространстве, основанном на принципах Шаблон:Не переведено 5. Время работы их алгоритма равно <math>O(mn \cdot \log(mn))</math> для двух ломаных с m и n отрезками.
Диаграмма свободного пространства
Важным средством вычисления расстояния Фреше между двумя кривыми является диаграмма свободного пространства, которую предложили Альт и ГодауШаблон:Sfn. Диаграмма свободного пространства между двумя кривыми для заданного порога расстояния ε — это двумерная область в пространстве параметров, состоящая из всех пар точек двух кривых, находящихся на расстоянии, не превосходящем ε:
<math>D_\varepsilon(A,B) := \{\,(\alpha,\beta)\in[0,1]^2\mid d( A(\alpha), B(\beta))\le\varepsilon \,\} </math>
Расстояние Фреше <math>F(A,B)</math> не превосходит ε тогда и только тогда, когда диаграмма свободного пространства <math>D_\varepsilon(A,B)</math> содержит путь из левого нижнего угла в правый верхний угол, монотонный как по горизонтали, так и по вертикали.
Варианты
Слабое расстояние Фреше — это вариант классического расстояния Фреше без требования монотонности движения вдоль кривых, собаке и её владельцу разрешается обратное движение. Альт и ГодауШаблон:Sfn описали простой алгоритм для вычисления слабого расстояния Фреше между ломаными, основанном на вычислении минимаксного пути в связанной решётке.
Дискретное расстояние Фреше, называемое также сцепленным расстоянием, — это аппроксимация метрики Фреше для ломаных, определённая Айтером и МаннилойШаблон:Sfn. Дискретное расстояние Фреше рассматривает только положения поводка в вершинах двух ломаных и никогда внутри ребра. Эта специальная структура позволяет вычислить дискретное расстояние Фреше за полиномиальное время с помощью простого алгоритма динамического программирования.
Если две кривые вложены в метрическое пространство, отличное от евклидова, такое как Шаблон:Не переведено 5, или вложены в евклидово пространство с препятствиями, расстояние между двумя точками на кривых естественно определить как длину кратчайшего пути между ними. Поводок в этом случае является геодезической, соединяющей две точки. Получившаяся метрика между кривыми называется геодезическим расстоянием ФрешеШаблон:SfnШаблон:SfnШаблон:Sfn. Кук и ВенкШаблон:Sfn описали алгоритм полиномиального времени вычисления геодезического расстояния Фреше между двумя ломаными в простом многоугольнике.
Если мы потребуем, чтобы поводок двигался непрерывно в окружающем метрическом пространстве, получим понятие гомотопное расстояние ФрешеШаблон:Sfn между двумя кривыми. Поводок не может «перепрыгивать» с одной позиции в другую и, в частности, не может «перепрыгивать» через препятствия и может «перелезать» через горы, только будучи достаточно длинным. Движение поводка описывает гомотопия между двумя кривыми. Чамберс с соавторамиШаблон:Sfn описал алгоритм полиномиального времени вычисления гомотопного расстояния Фреше между ломаными на евклидовой плоскости с препятствиями.
Примеры
Расстояние Фреше между двумя концентричными окружностями с радиусами <math>r_1</math> и <math>r_2</math> равно <math>|r_1 - r_2|</math>. Наибольший поводок нужен, когда владелец стоит, а собака бежит в противоположную точку окружности (<math>r_1 + r_2</math>), а наименьший поводок будет, когда владелец и собака движутся с одинаковой угловой скоростью вокруг окружности (<math>|r_1 - r_2|</math>).
Примечания
Литература
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:СтатьяШаблон:Недоступная ссылка
Литература для дальнейшего чтения
