ПРОСТОРОВІ ПЕРЕТВОРЕННЯ ТОЧКОВИХ МНОЖИН НА ЦІЛОЧИСЕЛЬНИХ РЕГУЛЯРНИХ СІТКАХ

Анотація

Роботу присвячено розробці узагальненого підходу до розробки методів просторових перетворень на цілочисельних регулярних сітках для розв’язання задач ефективної з точки зору час обробки точкових множин, що представлені в вигляді дискретизованих даних на регулярних сітках. Прикладами таких перетворень є просторова індексація та візуалізація на двовимірну площину. Постійне зростання як обсягів так і розмірності даних, що оброблюються в практичних задачах призводить до зростання вимог до обчислювальної ефективності алгоритмів, які використовуються для їх розв’язання. Існує широке коле задач, в яких використання просторових перетворень може бути використано для підвищення ефективності розрахунків, наприклад, зберігання та використання ресурсів, швидка обробка даних, візуалізація даних, підвищення швидкості сучасних алгоритмів інтелектуального аналізу даних. Іншими прикладами задачам є задачі покриття множини, пошук зображень за змістом, обробка геопросторових даних. Методи для оптимізації обчислювальної ефективності в алгоритмах розв’язання подібних задач найчастіше базуються на використання методів впорядковування точкових множин через використання просторових структур даних і алгоритмів їх обробки. В роботі представлено узагальнений підхід до створення методів просторових перетворень на основі методів просторової індексації цілочисельних регулярних сіток, який дозволяє зводити алгоритми обробки точкових даних до лінійної складності по часу незалежно від розмірності вхідних даних. В роботі запропоновані схеми просторових перетворень на основі лінійних та ступеневих функцій, а також на основі визначення належності точок до деякої області простору. Основою підходу є операції дискретизації та індексації точкових даних. В роботі розглянуто спосіб вирішення проблеми експоненційного зростання кількості комірок на цілочисельній регулярній сітці для зберігання точок. Запропоновано базові операції та алгоритми прямого та зворотного перетворень в метричних просторах. В роботі задано базові характеристики перетворень та наведено підхід до оцінювання ефективності перетворень на їх основі.Ключові слова: просторові перетворення, цілочисельна регулярна сітка, точкова множина, дискретизовані дані, просторова індексація, впорядковування точкових множин, візуалізація.