Abonnement à la biblothèque: Guest
Portail numérique Bibliothèque numérique eBooks Revues Références et comptes rendus Collections
Journal of Automation and Information Sciences
SJR: 0.275 SNIP: 0.59 CiteScore™: 0.8

ISSN Imprimer: 1064-2315
ISSN En ligne: 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

RÉSUMÉ

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.

RÉFÉRENCES

  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:

Solving Integrated Inverse Problems for Pseudoparabolic Multicomponent Distributed Systems
Journal of Automation and Information Sciences, Vol.39, 2007, issue 7
Ivan V. Sergienko, Vasiliy S. Deineka
On Solution of the Generalized Riccati Equations
Journal of Automation and Information Sciences, Vol.48, 2016, issue 11
Vladimir B. Larin
Hybrid Algorithm for Identification of Linear by States Hammerstein Model
Journal of Automation and Information Sciences, Vol.46, 2014, issue 1
Fedor G. Garashchenko, Olga G. Moroz
STOCHASTIC DYNAMIC RESPONSE ANALYSIS OF NONLINEAR STRUCTURES WITH GENERAL NONUNIFORM RANDOM PARAMETERS BY MINIMIZING GL2-DISCREPANCY
International Journal for Multiscale Computational Engineering, Vol.14, 2016, issue 3
Jianbing Chen, Pengyan Song, Xiaodan Ren
The Genetic Algorithms are a Modern Means of Searching Quasioptimal Solutions
Journal of Automation and Information Sciences, Vol.35, 2003, issue 9
Tadeush Witkowski, Arkadiush Antchak