Abo Bibliothek: Guest
Digitales Portal Digitale Bibliothek eBooks Zeitschriften Referenzen und Berichte Forschungssammlungen
Journal of Automation and Information Sciences
SJR: 0.275 SNIP: 0.59 CiteScore™: 0.8

ISSN Druckformat: 1064-2315
ISSN Online: 2163-9337

Volumes:
Volumen 52, 2020 Volumen 51, 2019 Volumen 50, 2018 Volumen 49, 2017 Volumen 48, 2016 Volumen 47, 2015 Volumen 46, 2014 Volumen 45, 2013 Volumen 44, 2012 Volumen 43, 2011 Volumen 42, 2010 Volumen 41, 2009 Volumen 40, 2008 Volumen 39, 2007 Volumen 38, 2006 Volumen 37, 2005 Volumen 36, 2004 Volumen 35, 2003 Volumen 34, 2002 Volumen 33, 2001 Volumen 32, 2000 Volumen 31, 1999 Volumen 30, 1998 Volumen 29, 1997 Volumen 28, 1996

Journal of Automation and Information Sciences

DOI: 10.1615/JAutomatInfScien.v52.i3.10
pages 1-12

Algorithm for Constructing Voronoi Diagrams with Optimal Placement of Generator Points Based on Theory of Optimal Set Partitioning

Elena M. Kiseleva
Oles Honchar Dnipro National University, Dnepr
Lyudmila L. Hart
Oles Honchar Dnipro National University, Dnepr
Olga M. Prytomanova
Oles Honchar Dnipro National University, Dnepr

ABSTRAKT

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.

REFERENZEN

  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, 2018, 50, No. 9, 1-24, DOI: 10.1615/JAutomatInfScien. v50.i9.10.

  2. Okabe A., Boots B., Sugihara K., Chiu S.N., Spatial tessellations: Concepts and applications of Voronoi diagrams, Second ed., John Wiley and Sons Ltd, West Sussex, England, 2000.

  3. Aurenhammer F., Klein R., Lee D., Voronoi diagrams and Delaunay triangulations, World Scientific Pub Co Inc, 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, 1995, 1, 247-259.

  5. Preparata F., Computational geometry: Introduction. Shamos M. [Russian translation], Mir, Moscow, 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, 2015, 51, No. 3, 325-335.

  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, 2015, 51, No. 4, 489-499.

  8. Shor N.Z., Minimization methods for non-differentiable functions, Springer series. Computational mathematics, Springer-Verlag, Berlin, 1985, 3.


Articles with similar content:

Algorithm of Solving of Nonlinear Continuous Multicomponent Problem of Optimal Set Partitioning with Placement of Subsets Centers
Journal of Automation and Information Sciences, Vol.44, 2012, issue 2
Elena M. Kiseleva, Viktoriya A. Stroyeva
Method of Solving Problem of Conditional Optimization on Combinatorial Set of Arrangements
Journal of Automation and Information Sciences, Vol.51, 2019, issue 8
Victor V. Semenov , Alla N. Nagornaya, Lyudmila N. Kolechkina
Homogenization of Optimal Control Problems of Coefficients of Linear Elliptic Equations
Journal of Automation and Information Sciences, Vol.29, 1997, issue 4-5
R. I. Korgut, A. I. Egorov
A Posteriori Synthesis of Optimal Control of Nonlinear Stochastic Structures
Journal of Automation and Information Sciences, Vol.31, 1999, issue 1-3
Vladimir A. Pogorelov, Sergey V. Sokolov
Admissible Approximation of Discrete Argument Functions and its Application to Data Compression
Journal of Automation and Information Sciences, Vol.31, 1999, issue 4-5
Nikolay P. Lepekha, I. A. Popiv, Nikolay Fedorovich Kirichenko