Распознавание сходства многоугольников в усиленной хаусдорфовой метрике
Описан алгоритм распознавания сходства многоугольников в метрике Фреше. Для заданных m-угольника, n-угольника и числа ε алгоритм определяет, превышает ли расстояние между ними порог ε. Известные алгоритмы решают эту задачу за время, линейно зависящее от (mxn)log(mxn), предлагаемый алгоритм — за врем...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2014 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/115806 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Распознавание сходства многоугольников в усиленной хаусдорфовой метрике / М.И. Шлезингер, Е.В. Водолазский, В.М. Яковенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 3. — С. 174-187. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| Резюме: | Описан алгоритм распознавания сходства многоугольников в метрике Фреше. Для заданных 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).
|
|---|