Распознавание сходства многоугольников в усиленной хаусдорфовой метрике

• Published in: Кибернетика и системный анализ
• Date: 2014
• Main Authors: Шлезингер, М.И., Водолазский, Е.В., Яковенко, В.М.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2014
• Subjects: Новые средства кибернетики, информатики, вычислительной техники и системного анализа
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/115806
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Распознавание сходства многоугольников в усиленной хаусдорфовой метрике / М.И. Шлезингер, Е.В. Водолазский, В.М. Яковенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 3. — С. 174-187. — Бібліогр.: 8 назв. — рос.

Описан алгоритм распознавания сходства многоугольников в метрике Фреше. Для заданных m-угольника, n-угольника и числа ε алгоритм определяет, превышает ли расстояние между ними порог ε. Известные алгоритмы решают эту задачу за время, линейно зависящее от (mxn)log(mxn), предлагаемый алгоритм — за время порядка (mxn). Описано алгоритм для розпізнавання схожості двох многокутників у метриці Фреше. Для заданих двох многокутників і числа ε алгоритм визначає, чи відстань між многокутниками більша ε. Відомі алгоритми розв’язують цю задачу за час, що лінійно залежить від (mxn)log(mxn). Описаний алгоритм розв’зує задачу за час порядку (mxn). 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 to solve this problem. For the proposed algorithm, it takes a time of order of (mxn).