Відстань Фреше

Відстань Фреше — міра подібності кривих, що враховує число і порядок точок уздовж кривих. Названо ім'ям французького математика Моріса Фреше.

Інтуїтивне визначення

Уявіть собі людину, що йде скінченним криволінійним шляхом і вигулює свого собаку на повідці, причому собака проходить іншим скінченним криволінійним шляхом. Кожен з них може змінювати свою швидкість, щоб не послаблювати повідець, але жоден із них не може рухатися назад. Відстань Фреше між двома кривими — це довжина найкоротшого повідця, достатня для того, щоб обидва могли пройти своїми шляхами від початку до кінця.

Зверніть увагу, що визначення симетричне відносно двох кривих: відстань Фреше була б такою ж, якби собака вигулювала свого господаря.

Формальне визначення

Нехай $S$ — метричний простір. Крива $A$ в просторі $S$ — це неперервне відображення одиничного відрізка в $S$, тобто. $A:[0,1]\rightarrow S$. Репараметризація $\alpha$ відрізка $[0,1]$ — це неперервна неспадна сюр'єкція $\alpha :[0,1]\rightarrow [0,1]$.

Нехай $A$ і $B$ — дві криві в $S$. Тоді відстань Фреше між $A$ і $B$ визначають як точну нижню межу за всіма репараметризаціями $\alpha$ і $\beta$ відрізка $[0,1]$ за всіма максимумами $t\in [0,1]$ відстаней у $S$ між $A(\alpha (t))$ і $B(\beta (t))$. У математичних позначеннях відстань Фреше $F(A,B)$ дорівнює

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

де $d$ — функція відстані простору $S$.

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

Метрика Фреше враховує потік двох кривих, оскільки пари точок, чия відстань впливає на відстань Фреше, неперервно проходять уздовж своїх відповідних кривих. Це робить відстань Фреше найкращою мірою подібності кривих порівняно з метрикою Гаусдорфа для довільної множини точок. Дві криві можуть мати малу відстань Гаусдорфа, але велику відстань Фреше.

Діаграма вільного простору червоної та синбої кривих. На відміну від наведеного вище визначення, яке використовує параметризацію відрізка [0,1] для обох кривих, у цьому прикладі криві параметризовано за довжиною кривої

Відстань Фреше та її варіації знаходять застосування в деяких задачах, від морфінгу та розпізнавання рукописного введення до розташування білкових структур. Альт і Годау першими описали алгоритм поліноміального часу для обчислення відстані Фреше між двома ламаними в евклідовому просторі, заснований на принципах параметричного пошуку. Час роботи їхнього алгоритму дорівнює $O(mn\cdot \log(mn))$ для двох ламаних з m та n відрізків.

Діаграма вільного простору

Важливим засобом обчислення відстані Фреше між двома кривими є діаграма вільного простору, яку запропонували Альт і Годау. Діаграма вільного простору між двома кривими для заданого порогу відстані ε — це двовимірна ділянка у просторі параметрів, що складається з усіх пар точок двох кривих, які лежать на відстані, що не перевищує ε:

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

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

Варіанти

Слабка відстань Фреше — це варіант класичної відстані Фреше без вимоги монотонності руху вздовж кривих, тобто, собаці та її власнику дозволяється зворотний рух. Альт і Годау описали простий алгоритм для обчислення слабкої відстані Фреше між ламаними, заснований на обчисленні мінімаксного шляху у пов'язаній решітці.

Дискретна відстань Фреше, звана також зчепленою відстанню, — це апроксимація метрики Фреше для ламаних, яку визначили Айтер і Манніло. Дискретна відстань Фреше розглядає лише положення повідця у вершинах двох ламаних і ніколи всередині ребра. Ця спеціальна структура дозволяє обчислити дискретну відстань Фреше за поліноміальний час за допомогою простого алгоритму динамічного програмування.

Якщо дві криві вкладені в метричний простір, відмінний від евклідового, такий як многогранний рельєф, або в евклідів простір із перешкодами, відстань між двома точками кривих природно визначити як довжину найкоротшого шляху між ними. Повідець у цьому випадку є геодезичною, яка з'єднує дві точки. Отриману метрику між кривими називають геодезичною відстанню Фреше. Кук і Венк описали алгоритм поліноміального часу обчислення геодезичної відстані Фреше між двома ламаними в простому многокутнику.

Якщо вимагати, щоб повідець рухався в навколишньому метричному просторі неперервно, отримаємо поняття гомотопної відстані Фреше між двома кривими. Повідець не може перестрибувати з однієї позиції в іншу і, зокрема, не може перестрибувати через перешкоди і може «перелазити» через гори, тільки маючи достатню довжину. Рух повідця визначає гомотопія між двома кривими. Чамберс зі співавторами описав алгоритм поліноміального часу обчислення гомотопної відстані Фреше між ламаними на евклідовій площині з перешкодами.

Приклади

Відстань Фреше між двома концентричними колами з радіусами $r_{1}$ і $r_{2}$ дорівнює $|r_{1}-r_{2}|$. Найбільший повідець потрібен, коли власник стоїть, а собака біжить у протилежну точку кола ($r_{1}+r_{2}$), а найменший повідець буде, коли власник і собака рухаються з однаковою кутовою швидкістю по колу ($|r_{1}-r_{2}|$).

Література

• Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, Joseph S. B. Mitchell, T. M. Murali. New similarity measures between polylines with applications to morphing and polygon sweeping // Discrete and Computational Geometry. — 2002. — Т. 28, вип. 4. — С. 535—569. — DOI:10.1007/s00454-002-2886-1.
• R. Sriraghavendra, K. Karthik, Chiranjib Bhattacharyya. Proc. 9th International Conference on Document Analysis and Recognition (ICDAR '07). — 2007. — С. 461—465. — DOI:10.1109/ICDAR.2007.121.
• Jiang Minghui, Xu Ying, Zhu Binhai. Protein structure-structure alignment with discrete Fréchet distance // Journal of Bioinformatics and Computational Biology. — 2008. — Т. 6, вип. 1. — С. 51—64. — DOI:10.1142/S0219720008003278. — PMID 18324745 .
• Helmut Alt, Michael Godau. Computing the Fréchet distance between two polygonal curves // International Journal of Computational Geometry and Applications. — 1995. — Т. 5, вип. 1—2. — С. 75—91. — DOI:10.1142/S0218195995000064.
• Thomas Eiter, Heikki Mannila. Computing discrete Fréchet distance. — Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994. — (Tech. Report CD-TR 94/64)
• Atlas F. Cook, Carola Wenk. Geodesic Fréchet distance with polygonal obstacles. — University of Texas at San Antonio, 2008. — (Tech. Report CS-TR-2008-0010)
• Anil Maheshwari, Jiehua Yi. Proc. 21st European Workshop on Computational Geometry. — 2005. — С. 41—44.
• Erin Wolf Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, Shripad Thite. Homotopic Fréchet distance between curves, or Walking your dog in the woods in polynomial time // Computational Geometry: Theory and Applications. — 2009. — Т. 43, вип. 3. — С. 295—311. — DOI:10.1016/j.comgeo.2009.02.008.^{[недоступне посилання з листопада 2017]}