АЛГОРИТМ ПОБУДОВИ ДІАГРАМ ВОРОНОГО З ОПТИМАЛЬНИМ РОЗМІЩЕННЯМ ТОЧОК–ГЕНЕРАТОРІВ НА ОСНОВІ ТЕОРІЇ ОПТИМАЛЬНОГО РОЗБИТТЯ МНОЖИН

• Дата: 2020
• Автори: Kiseleva, E.M., Hart, L.L., Prytomanova, O.M.
• Формат: Стаття
• Мова: English
• Опубліковано: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2020
• Теми: узагальнена діаграма Вороного; точки–генератори; оптимальне розбиття множин; недиференційовна оптимізація; r-алгоритм Н.З. Шора
• Онлайн доступ: https://jais.net.ua/index.php/files/article/view/454
• Назва журналу: Problems of Control and Informatics

An algorithm is proposed for constructing a generalized Voronoi diagram with optimal placement of a finite number of generator points in a bounded set of n-dimensional Euclidean space. The algorithm is based on the formulation of the corresponding continuous problem of optimal set partitioning with a partition quality criterion providing the corresponding form of the Voronoi diagram, and on the application of the apparatus of the optimal partitioning theory to solve this problem. Herewith, the effective method of non-differentiable optimization is used for the numerical solution of an auxiliary finite-dimensional optimization problem arising in the development of the method for solving the mentioned infinite-dimensional optimal partitioning problem. Namely, that is one of the variants of the generalized gradient descent method with space expansion in the direction of the difference of two successive generalized antigradients (Shor’s r-algorithm). The proposed algorithm for constructing a generalized Voronoi diagram with optimal placement of a finite number of generator points in a bounded set of n-dimensional Euclidean space has some advantages compared to those known in the scientific literature. It does not depend on the dimension of Euclidean space containing the original bounded set; it is applicable for large-scale problems (over 300 generator points); it works not only for Euclidean metrics, but also for Chebyshev, Manhattan and other ones; the complexity of the algorithm implementation for constructing a Voronoi diagram based on the proposed approach does not increase with an increase in the number of generator points. The results of software implementation of the developed algorithm are presented for constructing a standard Voronoi diagram with optimal placement of generator points, as well as some of its generalizations, such as additive, multiplicative and additive-multiplicative Voronoi diagrams with optimal placement of generator points.