Расстояние Фреше

Представим себе собаку, прогуливающуюся вдоль одной кривой, которую держит на поводке владелец собаки, идущий вдоль другой кривой. Оба проходят от начальной точки до конечной, меняя скорость, но не возвращаясь. Расстояние Фреше между этими двумя кривыми — это длина самого короткого поводка, с которым можно пройти кривые. Не самый короткий поводок, при котором можно пройти все пути, а самый короткий, при котором можно пройти путь.

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

Пусть ${\displaystyle S}$ — метрическое пространство. Кривая ${\displaystyle A}$ в пространстве ${\displaystyle S}$ — это непрерывное отображение единичного отрезка в ${\displaystyle S}$, т.е. ${\displaystyle A:[0,1]\rightarrow S}$. Репараметризация ${\displaystyle \alpha }$ отрезка ${\displaystyle [0,1]}$ — это непрерывная неубывающая сюръекция ${\displaystyle \alpha$ :[0,1]\rightarrow [0,1]} .

Пусть ${\displaystyle A}$ и ${\displaystyle B}$ — две кривые в ${\displaystyle S}$. Тогда расстояние Фреше между ${\displaystyle A}$ и ${\displaystyle B}$ определяется как точная нижняя граница по всем репараметризациям ${\displaystyle \alpha }$ и ${\displaystyle \beta }$ отрезка ${\displaystyle [0,1]}$ по всем максимумам ${\displaystyle t\in [0,1]}$ расстояний в ${\displaystyle S}$ между ${\displaystyle A(\alpha (t))}$ и ${\displaystyle B(\beta (t))}$. В математических обозначениях расстояние Фреше ${\displaystyle F(A,B)}$ равно

${\displaystyle F(A,B)=\inf _{\alpha ,\beta }\,\,\max _{t\in [0,1]}\,\,{\Bigg \{}d{\Big (}A(\alpha (t)),\,B(\beta (t)){\Big )}{\Bigg \}}}$,

где ${\displaystyle d}$ — функция расстояния пространства ${\displaystyle S}$.

Неформально, мы можем считать параметр ${\displaystyle t}$ «временем». Тогда ${\displaystyle A(\alpha (t))}$ является положением собаки, а ${\displaystyle B(\beta (t))}$ — положением владельца собаки по времени ${\displaystyle t}$ (или наоборот). Длина поводка между ними в момент времени ${\displaystyle t}$ равна расстоянию между ${\displaystyle A(\alpha (t))}$ и ${\displaystyle B(\beta (t))}$. Взятие инфимума по всем возможным репараметризациям отрезка ${\displaystyle [0,1]}$ соответствует выбору прогулки вдоль кривых, при которой максимальная длина поводка минимизируется. Ограничение, что ${\displaystyle \alpha }$ и ${\displaystyle \beta }$ не убывают, означает, что ни собака, ни её владелец не могут повернуть назад.

Метрика Фреше принимает во внимание течение двух кривых, поскольку пары точек, расстояние между которыми определяет расстояние Фреше, «пробегают» вдоль кривых. Это делает расстояние Фреше лучшей мерой похожести кривых по сравнению с метрикой Хаусдорфа для произвольного множества точек. Две кривые могут иметь маленькое хаусдорфово расстояние, но большое расстояние Фреше.

Диаграмма свободного пространства красной и синей кривых. В отличие от определения выше, которое использует параметризацию отрезка [0,1] для обоих кривых, в этом примере кривые параметризованы по длине кривой.

Расстояние Фреше и его вариации находят применение в некоторых задачах, от морфинга[1] и распознавания рукописного ввода[2] до расположения протеиновых структур[3]. Альт и Годау[4] первыми описали алгоритм полиномиального времени для вычисления расстояния Фреше между двумя ломаными в евклидовом пространстве, основанном на принципах параметрического поиска. Время работы их алгоритма равно ${\displaystyle O(mn\cdot \log(mn))}$ для двух ломаных с m и n отрезками.

Важным средством вычисления расстояния Фреше между двумя кривыми является диаграмма свободного пространства, которую предложили Альт и Годау[4]. Диаграмма свободного пространства между двумя кривыми для заданного порога расстояния ε — это двумерная область в пространстве параметров, состоящая из всех пар точек двух кривых, находящихся на расстоянии, не превосходящем ε:

${\displaystyle D_{\varepsilon }(A,B):=\{\,(\alpha ,\beta )\in [0,1]^{2}\mid d(A(\alpha ),B(\beta ))\leq \varepsilon \,\}}$

Расстояние Фреше ${\displaystyle F(A,B)}$ не превосходит ε тогда и только тогда, когда диаграмма свободного пространства ${\displaystyle D_{\varepsilon }(A,B)}$ содержит путь из левого нижнего угла в правый верхний угол, монотонный как по горизонтали, так и по вертикали.

Слабое расстояние Фреше — это вариант классического расстояния Фреше без требования монотонности движения вдоль кривых, собаке и её владельцу разрешается обратное движение. Альт и Годау[4] описали простой алгоритм для вычисления слабого расстояния Фреше между ломаными, основанном на вычислении минимаксного пути в связанной решётке.

Дискретное расстояние Фреше, называемое также сцепленным расстоянием, — это аппроксимация метрики Фреше для ломаных, определённая Айтером и Маннилой[5]. Дискретное расстояние Фреше рассматривает только положения поводка в вершинах двух ломаных и никогда внутри ребра. Эта специальная структура позволяет вычислить дискретное расстояние Фреше за полиномиальное время с помощью простого алгоритма динамического программирования.

Если две кривые вложены в метрическое пространство, отличное от евклидова, такое как многогранный рельеф, или вложены в евклидово пространство с препятствиями, расстояние между двумя точками на кривых естественно определить как длину кратчайшего пути между ними. Поводок в этом случае является геодезической, соединяющей две точки. Получившаяся метрика между кривыми называется геодезическим расстоянием Фреше[1][6][7]. Кук и Венк[6] описали алгоритм полиномиального времени вычисления геодезического расстояния Фреше между двумя ломаными в простом многоугольнике.

Если мы потребуем, чтобы поводок двигался непрерывно в окружающем метрическом пространстве, получим понятие гомотопное расстояние Фреше[8] между двумя кривыми. Поводок не может «перепрыгивать» с одной позиции в другую и, в частности, не может «перепрыгивать» через препятствия и может «перелезать» через горы, только будучи достаточно длинным. Движение поводка описывает гомотопия между двумя кривыми. Чамберс с соавторами[8] описал алгоритм полиномиального времени вычисления гомотопного расстояния Фреше между ломаными на евклидовой плоскости с препятствиями.

Расстояние Фреше между двумя концентричными окружностями с радиусами ${\displaystyle r_{1}}$ и ${\displaystyle r_{2}}$ равно ${\displaystyle |r_{1}-r_{2}|}$. Наибольший поводок нужен, когда владелец стоит, а собака бежит в противоположную точку окружности (${\displaystyle r_{1}+r_{2}}$), а наименьший поводок будет, когда владелец и собака движутся с одинаковой угловой скоростью вокруг окружности (${\displaystyle |r_{1}-r_{2}|}$).

• Mark de Berg. Computational Geometry, Two Selected Topics. — С. 11—75..
• Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk. Proc. 14th European Symposium on Algorithms. — Springer-Verlag, 2006. — Т. 4168. — С. 52—63. — (Lecture Notes in Computer Science). — doi:10.1007/11841036_8..
• Helmut Alt, Maike Buchin. Can we compute the similarity between surfaces? // Discrete and Computational Geometry. — 2010. — Т. 43. — С. 78—99. — doi:10.1007/s00454-009-9152-8. — arXiv:cs.CG/0703011..