Algorithm for constructing voronoi diagrams with optimal placement of generator points based on theory of optimal set partitioning

被引：0

作者：

Kiseleva E.M. ^{[1
]}

Hart L.L. ^{[1
]}

Prytomanova O.M. ^{[1
]}

机构：

[1] National Academy of Sciences of Ukraine, Oles Honchar Dnipro National University, Dnepr

来源：

Journal of Automation and Information Sciences | 2020年 / 52卷 / 03期

关键词：

Generalized voronoi diagram; Generator points; Non-differentiable optimization; Optimal set partitioning; Shor's algorithm;

D O I：

10.1615/JAutomatInfScien.v52.i3.10

中图分类号：

学科分类号：

摘要：

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 Voronoi diagram, and on the application of the apparatus of the optimal partitioning theory to solve this problem. Herewith, the efficient 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 problem of optimal set partitioning. 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 a scientific literature. It does not depend on a dimension of Euclidean space containing the initial bounded set; it is applicable for the 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 Voronoi diagram based on the proposed approach does not increase with increasing number of generator points. The results of software implementation of the developed algorithm are presented for constructing a standard Voronoi diagram with an 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. © 2020 by Begell House Inc.

引用

页码：1 / 12

页数：11

共 8 条

[1] Kiseleva E.M., The emergence and formation of the theory of optimal set partitioning for sets of the n-dimensional Euclidean space. Theory and Application, Journal of Automation and Information Sciences, 50, 9, pp. 1-24, (2018)
[2] Okabe A., Boots B., Sugihara K., Chiu S.N., Spatial tessellations: Concepts and applications of Voronoi diagrams, (2000)
[3] Aurenhammer F., Klein R., Lee D., Voronoi diagrams and Delaunay triangulations, (2013)
[4] Atamturk A., Nemhauser G.L., Savelsbergh M.W.P., A combined Lagrangian, linear programming and implication heuristic for large-scale set partitioning problems, Journal of Heuristics, 1, pp. 247-259, (1995)
[5] Preparata F., Computational geometry: Introduction, (1989)
[6] Kiseleva E.M., Koriashkina L.S., Theory of continuous optimal set partitioning problems as a universal mathematical formalism for constructing Voronoi diagrams and their generalizations, I. Theoretical foundations, Cybernetics and Systems Analysis, 51, 3, pp. 325-335, (2015)
[7] Kiseleva E.M., Koriashkina L.S., Theory of continuous optimal set partitioning problems as a universal mathematical formalism for constructing Voronoi diagrams and their generalizations, II. Algorithms for constructing Voronoi diagrams based on the theory of optimal set partitioning, Cybernetics and Systems Analysis, 51, 4, pp. 489-499, (2015)
[8] Shor N.Z., Minimization methods for non-differentiable functions, Springer series, Computational mathematics, (1985)

← 1 →