Просторові перетворення точкових множин на цілочисельних регулярних сітках

Abstract

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

The work is devoted to the development of a generalized approach to the development of methods of spatial transformations on integer regular grids for solving the problems of time-efficient processing of point sets presented in the form of discretized data on regular grids. Examples of such transformations are spatial indexing and visualization on a two-dimensional plane. The constant growth of both the volume and dimension of the data processed in practical problems leads to an increase in the requirements for the computational efficiency of the algorithms used to solve them. There is a wide range of tasks in which the use of spatial transformations can be used to increase the efficiency of calculations, for example, storage and use of resources, fast data processing, data visualization, increasing the speed of modern algorithms for intelligent data analysis. Other examples of tasks are set coverage tasks, image search by content, geospatial data processing. Methods for optimizing computational efficiency in algorithms for solving similar problems are most often based on the use of methods for ordering point sets through the use of spatial data structures and algorithms for their processing. The paper presents a generalized approach to creating methods of spatial transformations based on methods of spatial indexing of integer regular grids, which makes it possible to reduce point data processing algorithms to linear time complexity regardless of the dimension of the input data. The paper proposes schemes of spatial transformations based on linear and power functions, as well as on the basis of determining whether points belong to a certain region of space. The basis of the approach is the operations of discretization and indexing of point data. The paper considers a way to solve the problem of exponential growth of the number of cells on an integer regular grid for storing points. Basic operations and algorithms for direct and inverse transformations in metric spaces are proposed. In the paper, the basic characteristics of transformations are given and an approach to evaluating the effectiveness of transformations based on them is given.