Open AccessFrechet Similarity Between Two Ambiguously Defined Polygonal Lines
Author(s) -
Evgeniy Vodolazskiy
Publication year - 2021
Publication title -
control systems and computers
Language(s) - English
Resource type - Journals
eISSN - 2706-8153
pISSN - 2706-8145
DOI - 10.15407/csc.2021.01.029
Subject(s) - combinatorics , mathematics , similarity (geometry) , polygonal chain , set (abstract data type) , graph , directed acyclic graph , directed graph , discrete mathematics , computer science , artificial intelligence , geometry , image (mathematics) , regular polygon , programming language
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.