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...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Control systems & computers
Datum:	2021
1. Verfasser:	Vodolazskiy, Ye.V.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2021
Schlagworte:	Fundamental Problems in Computer Science
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/181250
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	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

id	nasplib_isofts_kiev_ua-123456789-181250
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
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Frechet Similarity Between Two Ambigiously Defined Polygonal Lines
spellingShingle	Frechet Similarity Between Two Ambigiously Defined Polygonal Lines Vodolazskiy, Ye.V. Fundamental Problems in Computer Science
title_short	Frechet Similarity Between Two Ambigiously Defined Polygonal Lines
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_sort	frechet similarity between two ambigiously defined polygonal lines
author	Vodolazskiy, Ye.V.
author_facet	Vodolazskiy, Ye.V.
topic	Fundamental Problems in Computer Science
topic_facet	Fundamental Problems in Computer Science
publishDate	2021
language	English
container_title	Control systems & computers
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
format	Article
title_alt	Розпізнавання схожості неоднозначно заданих ламаних ліній у метриці Фреше
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. Мета статті. Необхідно розробити алгоритм, який би за двома множинами ламаних ліній та заданому числу визначав би, чи існує в цих множинах така пара ламаних (по одній з кожної множини), що відстань Фреше між ними не перевищує задане число. Результати. В статті наведено алгоритм, який в якості вхідних даних отримує пару орієнтованих ациклічних графів, вершинами якого є точки метричного простору, а ребрами – прямолінійні відрізки, що з’єднують вершини, та додатнє число. Таким чином, кожний шлях на графі задає ламану лінію, а граф у цілому задає множину ламаних ліній. На виході алгоритм дає відповідь, чи існує в двох графах така пара ламаних, що відстань Фреше між ними не перевищує задане число. Час роботи алгоритму пропорційний добутку кількості ребер одного графа на кількість ребер другого.
issn	2706-8145
url	https://nasplib.isofts.kiev.ua/handle/123456789/181250
citation_txt	Frechet Similarity Between Two Ambigiously Defined Polygonal Lines / Ye.V. Vodolazskiy // Control systems & computers. — 2021. — № 1. — С. 29-34. — Бібліогр.: 9 назв. — англ.
work_keys_str_mv	AT vodolazskiyyev frechetsimilaritybetweentwoambigiouslydefinedpolygonallines AT vodolazskiyyev rozpíznavannâshožostíneodnoznačnozadanihlamanihlíníiumetricífreše
first_indexed	2025-12-02T09:53:39Z
last_indexed	2025-12-02T09:53:39Z
_version_	1850862140507815936

Frechet Similarity Between Two Ambigiously Defined Polygonal Lines

Institution

Ähnliche Einträge