Padalko V. Methods and algorithms for constructing fuzzy Voronoi diagrams based on the theory of optimal set partitioning

The dissertation is devoted to the development and substantiation of methods and algorithms for constructing fuzzy Voronoi diagrams using the theory of optimal set partitioning from n-dimensional Euclidean space into subsets. The mathematical theory of optimal set partitioning (OSP) today is a powerful tool for solving many theoretical and practically important problems, which are reduced in mathematical formulation to continuous problems of optimal partitioning of sets from Euclidean space (linear or nonlinear, static or dynamic, deterministic or stochastic, in certainty or fuzzy). Solving a number of model problems from these classes often leads to mathematical objects called Voronoi diagrams or Dirichlet partitions. Voronoi diagrams in two and three-dimensional spaces are used in various fields of applied sciences: crystallography, physics, astronomy, chemistry, microbiology, computer graphics, in solving problems of artificial intelligence, image recognition, etc. For constructing Voronoi diagrams, many different algorithms are developed, but all these algorithms are quite complicated. The mathematical apparatus for constructing Voronoi diagrams, which has a number of advantages compared to the famous approaches described in the scientific literature, is the theory of optimal set partitioning developed by O.M. Kiseleva. To solve the continuous OSP problems, a unified approach is proposed, which is based on the following idea. The original OSP problems, which are mathematically formulated as infinite-dimensional optimization problems, are reduced in a certain way (for example, through the Lagrange functional) to auxiliary finite-dimensional non-smooth maximization problems or non-smooth maximin problems, for numerical solutions of which modern effective methods of non-differentiable optimization are used, namely, different modifications of Shor’s r-algorithm. The vast majority of problems of the OSP theory were studied under certainty conditions. However, real situations, for which optimal set partitioning models are created, are most often characterized by a certain degree of uncertainty: in initial data, in conditions and goals. In these cases, the quality of decisions made in optimization models of set partitioning is directly dependent on the completeness of taking into account all uncertain factors that are essential for the consequences of the decisions made. It seems natural to generalize partitioning models under certainty conditions to the case of models under uncertainty conditions. To disclose uncertainty in such problems (i.e., to formalize uncertain information), the apparatus of the theory of fuzzy sets is used, based on the concept of a fuzzy set introduced by L.A. Zade, as well as the apparatus of fuzzy logic. The purpose of the work is to develop and substantiate methods and algorithms for constructing fuzzy Voronoi diagrams using the theory of optimal partitioning of sets of n-dimensional Euclidean space n E into subsets. By analogy with the classification of fuzzy OSP problems, two main types of fuzzy Voronoi diagrams are distinguished: Voronoi diagrams with fuzzy parameters and Voronoi diagrams, in which the set of points that form Voronoi cells are fuzzy sets (fuzzy cells). The solution of fuzzy OSP problems, as well as for deterministic OSP problems, leads to the construction of fuzzy Voronoi diagrams of two main types: Voronoi diagrams with fuzzy parameters and diagrams with fuzzy Voronoi cells. The possibility of applying the mathematical theory of optimal set partitioning to the construction of the Voronoi diagram and its various generalizations is shown. The mathematical and algorithmic apparatus for constructing various variants of the Voronoi diagram is based on the formulation of continuous problems of optimal set partitioning with partition quality criteria that provide the corresponding types of Voronois diagrams.