Frechet Similarity Between Two Ambigiously Defined Polygonal Lines

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

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2021
Автор: Vodolazskiy, Ye.V.
Формат: Стаття
Мова:English
Опубліковано: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2021
Назва видання:Control systems & computers
Теми:
Fundamental Problems in Computer Science
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/181250
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Frechet Similarity Between Two Ambigiously Defined Polygonal Lines / Ye.V. Vodolazskiy // Control systems & computers. — 2021. — № 1. — С. 29-34. — Бібліогр.: 9 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-181250
record_format dspace
spelling irk-123456789-1812502021-11-09T01:26:19Z Frechet Similarity Between Two Ambigiously Defined Polygonal Lines Vodolazskiy, Ye.V. Fundamental Problems in Computer Science 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. Мета статті. Необхідно розробити алгоритм, який би за двома множинами ламаних ліній та заданому числу визначав би, чи існує в цих множинах така пара ламаних (по одній з кожної множини), що відстань Фреше між ними не перевищує задане число. Результати. В статті наведено алгоритм, який в якості вхідних даних отримує пару орієнтованих ациклічних графів, вершинами якого є точки метричного простору, а ребрами – прямолінійні відрізки, що з’єднують вершини, та додатнє число. Таким чином, кожний шлях на графі задає ламану лінію, а граф у цілому задає множину ламаних ліній. На виході алгоритм дає відповідь, чи існує в двох графах така пара ламаних, що відстань Фреше між ними не перевищує задане число. Час роботи алгоритму пропорційний добутку кількості ребер одного графа на кількість ребер другого. 2021 Article 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 http://dspace.nbuv.gov.ua/handle/123456789/181250 519.6 en Control systems & computers Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language English
topic Fundamental Problems in Computer Science
Fundamental Problems in Computer Science
spellingShingle Fundamental Problems in Computer Science
Fundamental Problems in Computer Science
Vodolazskiy, Ye.V.
Frechet Similarity Between Two Ambigiously Defined Polygonal Lines
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.
format Article
author Vodolazskiy, Ye.V.
author_facet Vodolazskiy, Ye.V.
author_sort Vodolazskiy, Ye.V.
title Frechet Similarity Between Two Ambigiously Defined Polygonal Lines
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
publisher Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate 2021
topic_facet Fundamental Problems in Computer Science
url http://dspace.nbuv.gov.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 назв. — англ.
series Control systems & computers
work_keys_str_mv AT vodolazskiyyev frechetsimilaritybetweentwoambigiouslydefinedpolygonallines
first_indexed 2023-10-18T22:51:58Z
last_indexed 2023-10-18T22:51:58Z
_version_ 1796156636281176064

Схожі ресурси