КИБЕРНЕТИКА И СИСТЕМНЫЙ АНАЛИЗ
Международний научно-теоретический
журнал
Аннотация.
Описан алгоритм распознавания сходства многоугольников в метрике Фреше. Для заданных m-угольника, n-угольника и числа ε алгоритм определяет, превышает ли расстояние между ними порог ε. Известные алгоритмы решают эту задачу за время, линейно зависящее от (mxn)log(mxn), предлагаемый алгоритм — за время порядка (mxn).
Ключевые слова: вычислительная геометрия, метрика Фреше, усиленная метрика Хаусдорфа, вычислительная сложность, многоугольники.
Шлезингер Михаил Иванович, доктор физ.-мат. наук, профессор, главный научный сотрудник Международного научно-учебного центра информационных технологий и систем МОН и НАН Украины, Киев,
e-mail: schles@irtc.org.ua.
Водолазский Евгений Валериевич, младший научный сотрудник Международного научно-учебного центра информационных технологий и систем МОН и НАН Украины, Киев,
e-mail: waterlaz@gmail.com.
Яковенко Вячеслав Михайлович, инженер-программист Международного научно-учебного центра информационных технологий и систем МОН и НАН Украины, Киев,
e-mail: asacynloki@gmail.com.
