Frechet Similarity Between Two Ambigiously Defined Polygonal Lines

• Published in: Control systems & computers
• Date: 2021
• Main Author: Vodolazskiy, Ye.V.
• Format: Article
• Language: English
• Published: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2021
• Subjects: Fundamental Problems in Computer Science
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/181250
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Frechet Similarity Between Two Ambigiously Defined Polygonal Lines / Ye.V. Vodolazskiy // Control systems & computers. — 2021. — № 1. — С. 29-34. — Бібліогр.: 9 назв. — англ.

The paper considers the problem of comparing two polygonal lines that are not strictly defined. Instead, two sets of polygonal lines are given assets of paths on two acyclic directed graphs. The problem is to determine whether there exists a pair of lines each from its respective set such that the Frechet distance between them is not greater than a given number. An algorithm is given that solves the problem in time, were and are the sets of edges in each graph respectively. Мета статті. Необхідно розробити алгоритм, який би за двома множинами ламаних ліній та заданому числу визначав би, чи існує в цих множинах така пара ламаних (по одній з кожної множини), що відстань Фреше між ними не перевищує задане число. Результати. В статті наведено алгоритм, який в якості вхідних даних отримує пару орієнтованих ациклічних графів, вершинами якого є точки метричного простору, а ребрами – прямолінійні відрізки, що з’єднують вершини, та додатнє число. Таким чином, кожний шлях на графі задає ламану лінію, а граф у цілому задає множину ламаних ліній. На виході алгоритм дає відповідь, чи існує в двох графах така пара ламаних, що відстань Фреше між ними не перевищує задане число. Час роботи алгоритму пропорційний добутку кількості ребер одного графа на кількість ребер другого.