Construction of a generalized Voronoi diagram with optimal placement of generator points based on the theory of optimal set partitioning

E.M. Kiseleva; L.L. Hart; O.M. Prytomanova; S.V. Zhuravel

doi:10.30970/ms.53.1.109-112

E.M. Kiseleva Oles Honchar Dnipro National University, Dnipro, Ukraine
L.L. Hart Oles Honchar Dnipro National University, Dnipro, Ukraine https://orcid.org/0000-0003-2617-7851
O.M. Prytomanova Oles Honchar Dnipro National University, Dnipro, Ukraine
S.V. Zhuravel Oles Honchar Dnipro National University, Dnipro, Ukraine

DOI: https://doi.org/10.30970/ms.53.1.109-112

Keywords: Voronoi diagram; continuous problems of optimal set partitioning; Shor's r-algorithm

Abstract

The problem of construction of a generalized Voronoi diagram with optimal placement of a finite number of generator points in a bounded set of \textit{n}-dimensional Euclidean space is considered. A method is proposed for solving such a problem based on the formulation of the corresponding continuous problem of optimal partitioning of a set in \textit{n}-dimensional Euclidean space with a partition quality criterion that provides the corresponding form of the Voronoi diagram. Further, to solve such a problem, the developed mathematical and algorithmic apparatus is used, the part of which is Shor's \textit{r}-algorithm.

Author Biographies

E.M. Kiseleva, Oles Honchar Dnipro National University, Dnipro, Ukraine

Dean of the Faculty of Applied Mathematics, Doctor of Physical and Mathematical Sciences, Professor, Corresponding Member of NAS of Ukraine

L.L. Hart, Oles Honchar Dnipro National University, Dnipro, Ukraine

Department of Computational Mathematics and Mathematical Cybernetics, Professor, Doctor of Physical and Mathematical Sciences

O.M. Prytomanova , Oles Honchar Dnipro National University, Dnipro, Ukraine

Department of Computational Mathematics and Mathematical Cybernetics, Associate Professor, Candidate of Economic Sciences

S.V. Zhuravel, Oles Honchar Dnipro National University, Dnipro, Ukraine

Department of Computational Mathematics and Mathematical Cybernetics, Associate Professor, Candidate of Physical and Mathematical Sciences

References

Preparata F., Sheimos M., Computational geometry: an introduction, Springer; First Edition edition, 1993.

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 (2015), №4, 489–499. https://doi.org/10.1007/s10559-015-9740-y

Kiseleva E.M., Shor N.Z. Continuous problems of optimal set partitioning: theory, algorithms, applications, Kyiv: Naukova Dumka, 2005. (in Russian)

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