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