Frechet Similarity Between Two Ambigiously Defined Polygonal Lines
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 F...
Saved in:
| Published in: | Control systems & computers |
|---|---|
| Date: | 2021 |
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2021
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/181250 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| 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 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862659405388972032 |
|---|---|
| author | Vodolazskiy, Ye.V. |
| author_facet | Vodolazskiy, Ye.V. |
| citation_txt | Frechet Similarity Between Two Ambigiously Defined Polygonal Lines / Ye.V. Vodolazskiy // Control systems & computers. — 2021. — № 1. — С. 29-34. — Бібліогр.: 9 назв. — англ. |
| collection | DSpace DC |
| container_title | Control systems & computers |
| description | 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.
Мета статті. Необхідно розробити алгоритм, який би за двома множинами ламаних ліній та заданому числу визначав би, чи існує в цих множинах така пара ламаних (по одній з кожної множини), що відстань Фреше між ними не перевищує задане число. Результати. В статті наведено алгоритм, який в якості вхідних даних отримує пару орієнтованих ациклічних графів, вершинами якого є точки метричного простору, а ребрами – прямолінійні відрізки, що з’єднують вершини, та додатнє число. Таким чином, кожний шлях на графі задає ламану лінію, а граф у цілому задає множину ламаних ліній. На виході алгоритм дає відповідь, чи існує в двох графах така пара ламаних, що відстань Фреше між ними не перевищує задане число. Час роботи алгоритму пропорційний добутку кількості ребер одного графа на кількість ребер другого.
|
| first_indexed | 2025-12-02T09:53:39Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-181250 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2706-8145 |
| language | English |
| last_indexed | 2025-12-02T09:53:39Z |
| publishDate | 2021 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Vodolazskiy, Ye.V. 2021-11-08T17:33:17Z 2021-11-08T17:33:17Z 2021 Frechet Similarity Between Two Ambigiously Defined Polygonal Lines / Ye.V. Vodolazskiy // Control systems & computers. — 2021. — № 1. — С. 29-34. — Бібліогр.: 9 назв. — англ. 2706-8145 DOI: https://doi.org/10.15407/csc.2021.029 https://nasplib.isofts.kiev.ua/handle/123456789/181250 519.6 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. Мета статті. Необхідно розробити алгоритм, який би за двома множинами ламаних ліній та заданому числу визначав би, чи існує в цих множинах така пара ламаних (по одній з кожної множини), що відстань Фреше між ними не перевищує задане число. Результати. В статті наведено алгоритм, який в якості вхідних даних отримує пару орієнтованих ациклічних графів, вершинами якого є точки метричного простору, а ребрами – прямолінійні відрізки, що з’єднують вершини, та додатнє число. Таким чином, кожний шлях на графі задає ламану лінію, а граф у цілому задає множину ламаних ліній. На виході алгоритм дає відповідь, чи існує в двох графах така пара ламаних, що відстань Фреше між ними не перевищує задане число. Час роботи алгоритму пропорційний добутку кількості ребер одного графа на кількість ребер другого. en Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Control systems & computers Fundamental Problems in Computer Science Frechet Similarity Between Two Ambigiously Defined Polygonal Lines Розпізнавання схожості неоднозначно заданих ламаних ліній у метриці Фреше Article published earlier |
| spellingShingle | Frechet Similarity Between Two Ambigiously Defined Polygonal Lines Vodolazskiy, Ye.V. Fundamental Problems in Computer Science |
| title | Frechet Similarity Between Two Ambigiously Defined Polygonal Lines |
| title_alt | Розпізнавання схожості неоднозначно заданих ламаних ліній у метриці Фреше |
| title_full | Frechet Similarity Between Two Ambigiously Defined Polygonal Lines |
| title_fullStr | Frechet Similarity Between Two Ambigiously Defined Polygonal Lines |
| title_full_unstemmed | Frechet Similarity Between Two Ambigiously Defined Polygonal Lines |
| title_short | Frechet Similarity Between Two Ambigiously Defined Polygonal Lines |
| title_sort | frechet similarity between two ambigiously defined polygonal lines |
| topic | Fundamental Problems in Computer Science |
| topic_facet | Fundamental Problems in Computer Science |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/181250 |
| work_keys_str_mv | AT vodolazskiyyev frechetsimilaritybetweentwoambigiouslydefinedpolygonallines AT vodolazskiyyev rozpíznavannâshožostíneodnoznačnozadanihlamanihlíníiumetricífreše |