Водолазський Є. В. ЕФЕКТИВНІ МЕТОДИ ОБЧИСЛЕННЯ СХОЖОСТІ ЗОБРАЖЕНЬ В МЕТРИЦІ ФРЕШЕ

Робота присвячена проблемі обчислення відстані Фреше, як більш сильної метрики, ніж відстань Хаусдорфа, між різними класами підмножин метричних просторів, зокрема підмножин в R^2. Розглянуто проблеми обчислення відстані Фреше між замкненими ламаними лініями (багатокутниками), розгалуженими ламаними лініями (деревами), множинами ламаних ліній, заданих як шляхи на ациклічних орієнтованих графах, а також обчислення дискретної відстані Фреше між замкненими послідовностями (циклами). Запропоновано ефективний алгоритм розпізнавання, чи перевищує відстань Фреше між двома замкненими ламаними лініями (багатокутниками) задане число. Час роботи становить O(mn), де m,n – кількість прямолінійних відрізків у двох ламаних, відповідно. Запропоновано ефективний алгоритм обчислення значення дискретної відстані Фреше між двома замкненими послідовностями (циклами) з часом роботи O(mn log*(mn)), де log* – ітерований логарифм, а m,n – кількість точок в циклах. Розглянута ситуація, коли ламані лінія для обчислення відстані Фреше задано не однозначно, а як множини шляхів на ациклічному орієнтованому графі. Сформульована нова задача розпізнавання, чи існує така пара ламаних, кожна зі своєї множини, що відстань Фреше між ними не перевищує задане число. Запропоновано алгоритм, що розв’язує цю задачу за час O(mn), де m,n – кількість ребер в двох графах, відповідно. Сформульовано нове поняття близькості одного дерева до іншого дерева еталону. Близькість, хоча й не є метрикою, є числовою оцінкою більш слабкою ніж метрика Фреше, але більш сильною ніж метрика Хаусдорфа. Близькість одного дерева до іншого скінченна навіть для неізоморфних дерев, на відміну від метрики Фреше. Запропоновано поліноміальний алгоритм розпізнавання близькості дерева до еталону. Сформульована нова задача розпізнаванні безконфліктності двох ламаних ліній, що є в певному сенсі двоїстою до задачі розпізнавання схожості ламаних ліній в метриці Фреше. Запропоновано алгоритм розв’язку с оцінкою складності O(mn).