Inscrição na biblioteca: Guest
Portal Digital Begell Biblioteca digital da Begell eBooks Diários Referências e Anais Coleções de pesquisa
Journal of Automation and Information Sciences
SJR: 0.275 SNIP: 0.59 CiteScore™: 0.8

ISSN Imprimir: 1064-2315
ISSN On-line: 2163-9337

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

RESUMO

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.

Referências

  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