Cybernetics And Systems Analysis
International Theoretical Science
Journal
Abstract. An algorithm for testing the similarity of two polygons in the Frechet metric is described. For any two given polygons and a number ε, the algorithm determines whether the distance between them is greater than ε. For the known algorithms, it takes time that linearly depends on (mxn)log(mxn) to solve this problem. For the proposed algorithm, it takes a time of order of (mxn).
Keywords: computational geometry, Frechet distance, strengthened Hausdorff metric, computational complexity, polygon.
Шлезингер Михаил Иванович, доктор физ.-мат. наук, профессор, главный научный сотрудник Международного научно-учебного центра информационных технологий и систем МОН и НАН Украины, Киев,
e-mail: schles@irtc.org.ua.
Водолазский Евгений Валериевич, младший научный сотрудник Международного научно-учебного центра информационных технологий и систем МОН и НАН Украины, Киев,
e-mail: waterlaz@gmail.com.
Яковенко Вячеслав Михайлович, инженер-программист Международного научно-учебного центра информационных технологий и систем МОН и НАН Украины, Киев,
e-mail: asacynloki@gmail.com.
