=Paper=
{{Paper
|id=Vol-2386/paper12
|storemode=property
|title=An Algorithm to Construct Generalized Voronoi Diagrams with Fuzzy Parameters Based on the Theory of Optimal Partitioning and Neuro-Fuzzy Technologies
|pdfUrl=https://ceur-ws.org/Vol-2386/paper12.pdf
|volume=Vol-2386
|authors=Elena Kiseleva,Liudmyla Hart,Olha Prytomanova,Oleksandr Kuzenkov
|dblpUrl=https://dblp.org/rec/conf/momlet/KiselevaHPK19
}}
==An Algorithm to Construct Generalized Voronoi Diagrams with Fuzzy Parameters Based on the Theory of Optimal Partitioning and Neuro-Fuzzy Technologies==
https://ceur-ws.org/Vol-2386/paper12.pdf
An Algorithm to Construct Generalized Voronoi
Diagrams with Fuzzy Parameters Based on the Theory of
Optimal Partitioning and Neuro-Fuzzy Technologies
Elena Kiseleva [0000-0003-4303-1707], Liudmyla Hart [0000-0003-2617-7851],
Olha Prytomanova [0000-0003-1878-6120], Oleksandr Kuzenkov [0000-0002-6378-7993]
Oles Honchar Dnipro National University, Gagarin Avenue, 72, Dnipro, 49010, Ukraine
kiseleva47@ukr.net
Abstract. An algorithm to construct a generalized Voronoi diagram (VD) in the
presence of fuzzy parameters is proposed with optimal location of a finite
number of generator points in a bounded set of n-dimensional Euclidean space
n . The algorithm is based on the formulation of the corresponding continuous
problem of optimal partitioning of a set (OPS) from n into non-intersecting
subsets with a partitioning quality criterion providing the corresponding VD
form with fuzzy parameters. The algorithm was developed using a synthesis of
methods for solving OPS theory problems, neuro-fuzzy technologies and
modifications of the N.Z.Shor’s r-algorithm for solving non-smooth
optimization problems.
Keywords: generalized Voronoi diagram, problem of optimal partitioning of
sets, optimal location of generator points, neuro-fuzzy technologies, N.Z.Shor’s
r-algorithm, non-smooth optimization problems.
1 Introduction
As is known [1, 2], a Voronoi diagram (VD) of a given finite set M {1 , 2 ,..., N }
of points in a plane (space), which are called generator points, is a mathematical
object representing such a partitioning of a plane (space) at which each domain
(Voronoi cell) of this partitioning forms a set of elements located closer to one of the
points of set M than to any other point of this set.
Voronoi diagrams in two- and three-dimensional spaces are used in various
fields of applied sciences [3, 4]. Currently, there are several hundreds of references on
VD and their applications in various fields. Substantive reviews of some of them are
given in [3-5]. There one can also find a general review of recent technical results and
applications with links to primary sources. Despite the fact that many well-known
algorithms for VD constructing cost O( N log N ) time, and some of these algorithms
even use O( N ) time, all of them are very complex. As for the VD for the case of a
space of arbitrary dimension, its construction is associated with significant
algorithmic problems. Indeed, it is known [2] that for a given number N of generator
points, the number of elements needed to describe VD increases exponentially
depending on the space dimension.
This paper is devoted to describing an algorithm to construct a generalized VD
in the presence of fuzzy parameters with optimal placement of a finite number N of
generator points in a bounded set of n-dimensional Euclidean space n (n 2) .
The algorithm is developed on the basis of a synthesis of methods for solving OSP
theory problems (see [3-5]) with neuro-fuzzy technologies (methodologies) (see [6-
10]) and modifications of the N.Z.Shor’s r-algorithm for solving non-smooth
optimization problems [11, 12]. This algorithm is based on:
formulating the corresponding problem of optimal partitioning of a set (OPS)
of n into non-intersecting subsets with a partitioning quality criterion providing the
corresponding VD form with fuzzy parameters;
applying the mathematical and algorithmic apparatus described in [3] to
solve such a problem, which includes the N.Z.Shor’s r-algorithm [11, 12] as a part;
using a neuro-fuzzy technology [6-10].
The basis of the above mathematical and algorithmic apparatus is the
following general idea [3-5]. The initial OSP problems that are mathematically
formulated as infinite-dimensional optimization problems, are reduced through the
Lagrange functional to auxiliary finite-dimensional non-smooth maximization
problems or non-smooth max-min problems, for the numerical solution of which
modern efficient methods of non-differentiable optimization are used, namely, various
modifications of the Shor's r-algorithm. The peculiarity of this approach is the fact
that the solution of the initial infinite-dimensional optimization problems can be
obtained analytically in an explicit form, and the analytic expression can include
parameters that are sought as an optimal solution of the above-mentioned auxiliary
finite-dimensional optimization problems with non-smooth target functions.
2 Review of the Literature
The algorithms to construct the standard VD with fuzzy parameters and its various
generalizations that are proposed in [3-5] and in cited there sources have some
advantages compared with those known in scientific literature [2, 13-20]:
− do not depend on the dimension of space Еn containing the partitionable
bounded set into subsets (the problem is only reduced to the calculation of
multidimensional integrals);
− do not depend on the geometry of the partitionable set;
− due to their high calculation speed, they are applicable for large dimensional
problems (100, 200, 300 or more generator points);
− are applicable not only for the Euclidean metric, but also for the metrics of
Chebyshev, Manhattan and others;
− the complexity of VD constructing algorithms based on the described
approach does not increase while increasing numbers of generator points;
− are applicable to the construct not only VD with given number of generator
points with their fixed location, but also with the optimal location of these points in a
bounded set of space Еn;
− the result of this universal approach is the ability to easily construct not only
the already known VD, but also new ones.
The universality of proposed in [3-5] approach to construct VD is confirmed
by that models and methods to solve OSP problems can be generalized to the case of
fuzzy specification of initial parameters of the problem or to the case of requirement
of a fuzzy partitioning of the set, where VD also may be fuzzy.
We first give some information from [3-5] on constructing generalized VD
with clear parameter on the basis of the above-mentioned mathematical apparatus.
As is known [2, 4], the standard (classical) Voronoi diagram of a finite set
M {1 , 2 ,..., N } En of generator points i (i(1) , i(2) ,..., i( n) ) , i 1, N , in n-
dimensional Euclidean space n (n 2) is the set of Voronoi polytopes:
Vor i x n : c x, i c x, j , j 1, N , j i , i 1, N , (1)
predefined points 1 ,..., N , where c x, y is a metric in n , which may be defined as
Euclidean, Manhattan and Chebyshev one [4]. In other words, VD of a finite set
M {1 , 2 ,..., N } from n (n 2) is the following set:
Vor Vor i , (2)
i
where mes Vor (i ) Vor ( j ) 0 , i, j 1, N (i j ) ; mes() is a Lebesgue
measure. n space partitioning into Voronoi polytopes Vor i , i 1, N of given set
M {1 , 2 ,..., N } is monosemantic.
A brief review of some generalizations of the standard VD available in the
scientific literature is given in book [4], for example:
– Additively Weighted VD of a set M {1 , 2 ,..., N } En :
AW Vor AW Vor i ,
i
AW Vor (i ) x n : с( x, i ) wi с( x, j ) w j , j 1, N , j i , i 1, N ,
where each generator point i M has a weight wi 0 ( i 1, N ) added to the
function specifying the distance while measurement;
– Multiplicatively Weighted VD of a set M {1 , 2 ,..., N } En :
MW Vor MW Vor i ,
i
where each Voronoi polytopes
MW Vor (i ) x n : с( x, i ) / wi с( x, j ) / w j , j 1, N , j i ,
i 1, N , is a set of points in space, the weighted distance from which to the generator
point i M does not exceed the weighted distance to any other point of M ( wi 0 ,
i 1, N as before are given weights).
Some other generalizations of the standard VD (1), (2) are also mentioned in
[4] such as the Laguerre diagram (Power VD), approximate (fuzzy) VD, VD with
constraints on the power of generator points, dynamic VD etc. There is also a table of
correspondence between a specific VD version with clear parameters and the
mathematical model of the OSP problem, the solution of which gives this diagram.
3 Problem Statement
We now turn to the mathematical formulation of the problem of constructing a
generalized VD in the presence of fuzzy parameters with the optimal location of a
finite number of generator points.
Let be some given bounded set from n and let 1 , 2 ,..., N be a finite set
of generator points in . In cases when the location of points 1 , 2 ,..., N in is
unknown and they need to be located (selected) in , we enter another VD version
on set n , namely, VD of a finite number of points optimally located in a
bounded set.
We define [4] the Voronoi diagram of a finite number of generator points
1 , 2 ,..., N optimally located in a bounded set n with fuzzy parameters as a
set of Voronoi polytopes
Vor i x n : c x, i / wi ai c x, j / w j a j , i j, j 1, N , (3)
i 1, N ,
of points 1 , 2 ,..., N where the total weighted distance from points of set to
corresponding generator points 1 ,..., N is minimal, so the functional
N
F 1 ,..., N (c( x, ) / w a )dx
i i i (4)
i 1 Vor ( i )
gets the minimum value. Here wi 0 ( i 1, N ) are given numbers (weights); ai 0
( i 1, N ) are given numeric parameters that are fuzzy and will be formalized using
the bell-shaped membership function [6, 7]. We will consider parameters ai , i 1, N ,
in (4) as parameters depending on fuzzy factors j , j 1, q in the form
ai ai (1 ,..., q ) . For example, in terms of the well-known location-allocation
problem with fuzzy parameters, parameter ai ( i 1, N ) makes sense of a cost of the
i -th enterprise to produce a unit of output and depends on fuzzy factors j , j 1,3 ,
where 1 is a cost of production means (production capacity and means of labor); 2
is a cost of labor resources; 3 is a cost of natural resources (raw materials and
energy).
Note: By specifying values of parameters w1 ,..., wN and a type of function
c( x, i ) in formula (4), one can obtain various VD versions in the presence of fuzzy
parameters with the optimal location of generator points (multiplicatively weighted,
additively weighted, etc.).
We present an approach to constructing VD with fuzzy parameters, based on
applying the apparatus of the theory of continuous OSP problems [3] and neuro-fuzzy
technologies [6-10].
To do this, we first formulate the corresponding problem of optimal
partitioning of a set from n-dimensional Euclidean space Еn into subsets with fuzzy
parameters in the target functional and with previously unknown coordinates of some
specific for each subset points, called "centers" of subsets. Such a problem is a
generalization of the problem from [3].
Let Ω be a bounded, Lebesgue measurable set in n-dimensional Euclidean
space. We name a set of Lebesgue measurable subsets 1 ,..., N from n as a
possible partitioning of set Ω into its non-intersecting subsets 1 ,..., N if
i , mes i j 0, i, j 1, N (i j ) ,
N
(5)
i 1
where mes is a Lebesgue measure.
We denote [3] by N the class of all possible partitions of a set Ω into non-
intersecting subsets 1 ,..., N that is
i , mes i j 0, i, j 1, N (i j ) .
N
N 1 ,..., N :
i 1
We introduce the functional
N
F 1 ,..., N , 1 ,..., N (c( x, i ) / wi ai ) dx (6)
i 1 i
where c x, i is a given real function bounded on Ω×Ω, measurable by
x x(1) ,..., x( n) for any fixed i i(1) ,..., i( n) , for each i 1, N ; wi 0
( i 1, N ) are given numbers (weights); ai 0 ( i 1, N ) are given fuzzy numeric
parameters.
Here and in the following, integrals are understood in the sense of Lebesgue.
We assume that the measure of the set of boundary points of subsets i , i 1, N , is
equal to zero.
We name the following problem as a continuous problem of optimal
partitioning of a set Ω from Еn into its non-intersecting subsets 1 ,..., N (some
of which may be empty) with fuzzy parameters in the target functional with
finding the coordinates of centers 1 , 2 ,..., N of these subsets, respectively [3].
Problem A. To find min F 1 ,..., N , 1 ,..., N ,
{1 ,..., N } N
,
{1 ,..., N } N
where the functional F {1 ,..., N },{1 ,..., N } is defined by (6); the coordinates
i(1) ,..., i( n) of centers i i(1) ,..., i( n) i , i 1, N are not predefined and should
be determined.
We define a pair {1 ,..., N }, {1 ,..., N } that minimizes functional (6) on
set N N as an optimal solution to Problem A. Wherein partitioning
{ ,..., } N we define as an optimal partitioning of the set n into N
1 N
subsets, and set 1 ,..., N N of centers i i , i 1, N as optimal centers
of the subsets i , i 1, N in Problem A.
Let us illustrate a partitioning of Ω Е2 into three subsets Ω1, Ω2, Ω3 with
corresponding centers 1 , 2 , 3 on Fig.1.
Fig.1. Partitioning of set Ω into three subsets
4 Materials and Methods
To solve Problem A for each fixed ai ( i 1, N ), we introduce the characteristic
functions of subsets i :
1, x i ,
i ( x) i 1, N ,
0, x \ i ,
and rewrite Problem A in terms of characteristic functions in the following form.
N
Problem B. To find min
(λ(),τ)
N
i 1
(c(x, τi ) / wi ai ) λi (x) dx ,
N
where {( x) (1 ( x),..., N ( x)) : λ*i (x) 1 for a.a. x , λi (x)=0 1
i 1
for a.a. x , i 1, N } ; τ=τ1 ,...,τ N Ω ... Ω N .
N
For Problem B, the theorem was proved in [3], which established the form of
an optimal solution (λ (), τ ) .
To remove fuzziness in Problem A, we apply the method of neuro-linguistic
identification [6]. Since, as stated above, parameters ai , i 1, N , in (6) depend on
fuzzy factors j , j 1, q in the form ai ai (1 ,..., q ) , we rewrite Problem A with
fuzzy parameters as follows:
N
(c( x, ) / w a ( ,..., ))dx
i 1 i
i i i 1 q min
{1 ,..., N } N
,
{1 ,..., N } N
under condition (5).
To simplify the description of the neuro-linguistic identification method
proposed in [6], we denote each parameter ai , i 1, N as a and consider the
functional dependence of an output a on the identification object inputs 1 ,..., q in
the form:
a a(), (1 ,..., q ) . (7)
For the identification problem, we assume to be known: domains of inputs
1 ,..., q , a range of output a change for (7), and expert-experimental information
about the dependency (7) in the form of a sample of data on the object inputs and
output. The problem of identifying (recovering) a complex nonlinear dependence of
the form (7) is considered as constructing an object model from expert-experimental
data on the input-output interrelationships and is usually solved in two stages [7-10]:
– structural identification: the formation of a fuzzy knowledge base about an
object and building on its basis a fuzzy object model with several inputs and one
output that roughly reproduces the dependence of an output on inputs using the
linguistic rules "IF-THEN" generated from experimental data;
– parametric identification (customization): search for such parameters of a
fuzzy model that minimize the deviation of model values from experimental ones.
The first stage of the neuro-linguistic identification method (structural
identification), which implies constructing a fuzzy model of an object with several
inputs and one output, consists of the following blocks: fuzzification, fuzzy inference,
defuzzification. At the fuzzification stage, in order to find dependence (7) in an
explicit form, we will consider input variables i , i 1, q and output variable a as
linguistic variables, for the evaluation of which we will use terms from the following
term sets [7]:
– D {Dk } is a term-set of variable a , where Dk is the k-th linguistic term of
variable a , k 1, L ; L is a number of different classes of output a ; for each class
Dk we define its center dk Dk ;
– i {ir } is a term-set of variable i , where ir is the r-th linguistic term
of variable i , i 1, q; r 1, t ; t is a number of terms in term-set i of variable i .
We obtain values of linguistic terms Dk and ir based on expert-linguistic
information about the modeled object. We define each term, like a fuzzy set, by its
bell-shaped membership function in the form (10) below. The constructed fuzzy
knowledge base based on expert-linguistic information about the modeled object
consists of production rules p kj (1 , 2 ,..., q ) and is used when executing a fuzzy
inference block (here k ( k 1, L ) is an output a class number; j ( j 1, sk ) is a
rule number in the k -th class; sk is a number of rules in the k-th class).
As a result of executing the fuzzy inference block, we obtain the membership
function D (a) of output variable a to class Dk in the form
k
sk k sk
p j ( 1 , 2 ,..., q ), if p j ( 1 , 2 ,..., q ) 1,
k
D (a) j 1 j 1 (8)
1, otherwise,
k
where
q
p kj ( 1 , 2 ,..., q ) v kj ijk ( i ), j 1, sk , k 1, L , (9)
i 1
1
ijk ( i ) 2
, i 1, q , (10)
i bijk
1
ek
ij
v j is a weight of the j -th rule in the k -th class of output a ; ijk ( i ) is the bell-
k
shaped membership function of variable i to term ir in the k -th class of output a ;
bijk is a maximum coordinate, eijk is a concentration coefficient of this membership
function ( j 1, sk ; k 1, L ; i 1, q; r 1, t ).
At the defuzzification stage, in order to obtain an accurate (clear) value of the
output variable, we apply the discrete analogue of the center-of-gravity method [7]:
L
d (a) k Dk
a k 1L . (11)
(a)
k 1
Dk
Thus, we have constructed a fuzzy model of object (7) in the form of relations
(8) - (11), which, as noted above, roughly describes the desired relationship (7).
At the second stage of the neuro-linguistic identification method (parametric
identification, customization), we will apply the methodology developed in [6] using
the N.Z. Shor’s r-algorithm [11, 12] to optimize the parameters of model (8) - (11).
As a result of solving this optimization problem, we obtain such values vkj for the
weights of rules (9) and bijk , eijk for the parameters of membership functions (10),
for which the deviation of experimental data from the model ones obtained after
customizing the fuzzy object model (7) reaches the minimum value.
In relations (8) - (11), we take for D (a) , p kj (1 , 2 ,..., q ) , ijk ( i ) their
k
values, which are calculated at the optimal values vkj , bijk , eijk of the parameters
obtained after customization, carried out using the N.Z.Shor’s r-algorithm [11, 12].
We present below theorem based on the results from [3, 6], which sums up our
reasoning and will be used later in the formulation of the algorithm to solve
Problem A.
Theorem. Optimal solution of Problem B has a form
* ( x) (*1 ( x),..., *i ( x),..., *N ( x)) , where for a. a. x
1, c( x, *i ) / wi ai c( x, * j ) / w j a j ,
*i ( x) j 1, N (j i), then x *i , i 1, N (12)
0, otherwise,
and *1 ,..., *N are an optimal solution of the problem
G() min[c( x, i ) / wi ai ]dx min, N . (13)
i 1, N
Here, each parameter ai ( i 1, N ) named earlier as output a depending on inputs
1 ,..., q in the form a a() , (1 ,..., q ) , is calculated by the following
formulas:
L
d (a)
k
Dk
a k 1 L , (14)
Dk (a)
k 1
where
sk k sk
p j ( 1 , 2 ,..., q ), p ( , ,..., ) 1,
k
if
(a) j 1
j 1 2 q
Dk j 1 (15)
1, otherwise,
q
pkj ( 1 , 2 ,..., q ) vkj ijk ( i ), (16)
i 1
1
ijk ( i ) 2
, i 1, q; j 1, sk ; k 1, L. (17)
i bijk
1
ek
ij
Here we present an algorithm to solve Problem A with neuro-linguistic
identification of fuzzy parameters ai , i 1, N , which is based on the above Theorem
and the most efficient (of the known methods of non-smooth optimization) method of
generalized gradient descent with space expansion in the direction of the difference of
two successive generalized anti-gradients (or the so-called N.Z.Shor’s r-algorithm
[11, 12]) for solving problem (13), dual to Problem B, with the non-differentiable
functional G() .
The idea of generalized gradient descent methods with space expansion is
based on successive constructing linear operators that change the metric of space, and
on choosing the descent direction corresponding to the anti-gradient in space with a
new metric.
In the iterative formula of the r-algorithm [11], which has the form
k 1 k hk Bk1 Bk1 gG k , k 0,1, 2,...,
T
(18)
B k 1 is an operator that maps transformed space into the main space EN ( B I is 0
identity matrix); hk is a stepping factor chosen from the condition of function G
minimum towards Bk 1 Bk1 gG k ; gG k is a generalized gradient of function
G() at point k .
Here we use the r-algorithm in H-form [11], where H k is a symmetric matrix
such that H k Bk BkT , and the iteration formula (18) is defined as
H k 1 gG k
k 1 k hk , k 0,1, 2,...,
H g , g
k 1 G
k
G
k
where
H k k Tk H k
H k 1 H k 1/ k2 1 ; k gG k gG k 1 .
H k k , k
Coefficient αk of space expansion is define as 3. To adjust stepping factor hk , the
adaptive method is used described in [11].
We define the і-th component of generalized gradient vector
gG gG1 ,..., gGi ,..., gGN of function
G() min [c( x, i ) / wi ai ] dx,
i 1,..., N
at point as
gGi gci x; i ( x)dx, i 1, N , (19)
where gci x, is the і-th component of vector of generalized gradient gC x, . In
formulas (19), i ( x) , i 1, N , is determined for almost all x as follows:
1, c( x, i ) / wi ai c( x, j ) / w j a j ,
i ( x) j 1,..., N (j i), then x i , (20)
0, otherwise,
where ai , i 1, N , are calculated by formulas (14) - (17).
4.1 Algorithm
Step 1. We enclose set Ω in n-dimensional parallelepiped П. Then we cover
parallelepiped П with rectangular grid and define initial approximation (0) . Then
we calculate (0) x in grid nodes by formulas (20) at (0) taking into account
formulas (14)-(17) to find parameter a ; we also calculate gG by formulas (19) at
x (0) x , (0) , select h0 0 and find
0 H1 gG 0
h0
1
,
0 0
H1 gG , gG
where РП is a projection operator on П. Then we go to the following step.
Step (k+1), k =1, 2,….
1. Calculate k x using formula (20), taking into account formulas (14) -
(17) for calculating parameter a , with k .
2. Find values of gG by formulas (19) with x ( k ) x , ( k ) .
3. Carry out the (k+1)-th step by the iteration formula [12]
k 1 k H k 1 gG k
hk ,
k
H k 1 gG , gG
k
4. Go to point 5 if
k k 1 , 0 , (21)
otherwise proceed to the (k+2)-th step of algorithm.
5. Assume * x x , * (l ) , where l is an iteration number at which
l
(21) holds true.
6. Calculate G() from (13) by the formula
G() min [c( x, i ) / wi ai ]dx ,
i 1,..., N
with * and ai , i 1, N , calculated by formulas (14)-(17).
The algorithm is described.
Thus, as a result of solving Problem A by the described algorithm based on the
above Theorem, we obtain a set of Voronoi polytopes (3) of generator points i ,
i 1, N :
Vor i x n : c x, i / wi ai c x, j / w j a j , i j, j 1, N ,
but instead of standard VD (1), in which points 1 ,..., N are fixed and parameters ai ,
i 1, N , are clear, a solution of the finite-dimensional optimization problem
G() min [c( x, i ) / wi ai ]dx min, N ... ,
i 1,..., N
N
is required to find the coordinates of generator points 1 ,..., N that are optimally
located in Еn . This optimization problem contains a non-differentiable target
function G() and parameters ai , i 1, N , reconstructed using the neuro-linguistic
identification method [6].
5 Numerical validation
Let us illustrate the algorithm operation to solve a Problem A for from E2 with
fuzzy parameters in the target functional by example of constructing a generalized
additive VD with fuzzy parameters and with locating N=5 generator points in the set
{( x(1) , x(2) ) E2 : 0 x(1) 1;0 x(2) 1} .
We note first that, as a result of solving Problem A with clear parameters by
the described algorithm a generalized additive VD has constructed with located five
generator points *1 ,..., *5 in and specified clear values of parameters a1 0,07 ;
a2 0,1 ; a3 0,38 ; a4 0, 2 ; a5 0 . Function c( x, i ) of distance from a point
x ( x(1) , x(2) ) to a generator point i (i(1) , i(2) ) was taken as follows:
c( x, i ) ( x(1) i(1) )2 ( x (2) i(2) ) 2 , i 1,5 . As a result of the described algorithm
operation, in 46 iterations we also obtained:
maximum value of functional G() from (13), equal to 0,26722;
minimum value of functional F of Problem A, equal to 0,26789.
This VD is presented in Fig. 2, where the solid line indicates boundaries of
subsets i , i 1,5 , and the «● » symbol indicates an optimal coordinates of generator
points: *1 =(0,28439; 0,23794); *2 =(0,19985; 0,76565); *4 =(0,81255; 0,14963);
*5 =(0,70583; 0,65526). At that, instead of partitioning into N=5 subsets, the
partitioning into four subsets turned out to be optimal: subset 3 turned out to be
empty, since the value a3 is much greater than ai , i 1,5 . It is easy to see that the
boundaries between the different cells of the additive VD presented in Fig. 2 are, as
proved in [3], either segments of hyperbola branches, if ai a j , or straight lines, if
ai a j , i, j 1,5 . In case ai a j , the Voronoi cells are convex polygons.
2
5
1
4
Fig.2. Voronoi diagrams for the model problem
6 Results and Discussion
We now turn to illustrating the approach described in this paper to solve the same
problem, but with fuzzy parameters ai , i 1,5 , in the target functional.
After applying the neuro-linguistic identification method to reconstruct (before
customization) parameters ai , i 1,5 , we got the following their values:
a1 0,07493 ; a2 0,19432 ; a3 0,33743 ; a4 0, 21138 ; a5 0,04007 . Further,
as a result of applying the described algorithm to solve Problem A with these
reconstructed values of parameters ai , i 1,5 , in 44 iterations we obtained:
additive VD with located in generator points *1 ,..., *5 , that is presented
in Fig. 2, where the dashed line indicates boundaries of subsets i , i 1,5 , and the
«■ » symbol indicates an optimal coordinates of the corresponding generator points:
*1 =(0,28883; 0,27976); *2 =(0,17024; 0,80697); *4 =(0,81631; 0,16100);
*5 =(0,69535; 0,68627);
maximum value of functional G() from (13), equal to 0,30075;
minimum value of functional F of Problem A, equal to 0,30299.
And finally, after reconstructing values of parameters ai , i 1,5 , using the
neuro-linguistic identification method [6] and after the subsequent applying the
described above algorithm to solve the considered Problem A with the reconstructed
after customizing values of parameters a1 0,07000 ; a2 0,10000 ; a3 0,38000 ;
a4 0,20000 ; a5 0,00000 , in 46 iterations, the same results were obtained (within
the specified accuracy 0,0001 ), as for the case with clear parameters, namely:
the corresponding VD presented in Fig. 2, where the solid line indicates
boundaries of the obtained subsets i , i 1,5 , and the «●» symbol indicates an
optimal coordinates of generator points: *1 =(0,28439; 0,23794); *2 =(0,19985;
0,76565); *4 =(0,81255; 0,14963); *5 =(0,70583; 0,65526);
maximum value of functional G() from (13), equal to 0,26722;
minimum value of functional F of Problem A, equal to 0,26789.
Comparing the numerical and graphical results of solving this model problem,
which are obtained for clear parameters a1 ,..., a5 in the target functional and for fuzzy
parameters a1 ,..., a5 reconstructed using the neuro-linguistic identification method,
we see that optimal solutions of these problems coincide with the sufficient degree of
accuracy. That is, the proposed approach to construct a generalized VD with fuzzy
parameters is reasonable and gives reliable results.
7 Conclusions
A new method and algorithm to construct a generalized VD in the presence of fuzzy
parameters with the optimal location of a finite number of generator points in a
bounded set of n are proposed. The method is based on formulating the
corresponding problem of optimal partitioning of a set of n into non-intersecting
subsets with locating the centers of these subsets with fuzzy parameters in the target
functional and with a partitioning quality criterion that provides the corresponding
form of VD with fuzzy parameters. The method of solving the above-mentioned OSP
problem is based on applying the mathematical apparatus developed in [3] and on
using the neuro-linguistic identification method developed in [6] to obviate fuzziness
in the OPS problem.
References
1. Voronoi G.F. Collected Works // Izd. Akad. Nauk UkrSSR, Kiev, vol. 2 (1952) [in
Russian]
2. Preparata F., Sheimos M. Computational geometry: an introduction. Springer;
First Edition edition, 390 p. (1993)
3. Kiseleva E.M., Shor N.Z. Сontinuous problems of optimal set partitioning: theory,
algorithms, applications. Kyiv: Naukova Dumka, 564 p. (2005) [in Russian].
4. Kiseleva Е.М., 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, vol. 51, № 3, pp. 325-335 (2015). DOI 10.1007/s10559-015-
9725-x.
5. Kiseleva Е.М., 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, vol. 51, № 4, pp. 489-499 (2015). DOI: 10.1007/s10559-015-
9740-y.
6. Kiseleva E.M., Pritomanova O.M., Zhuravel S.V. Algorithm for Solving a
Continuous Problem of Optimal Partitioning with Neurolinguistic Identification of
Functions in Target Functional // Journal of Automation and Information Science,
vol. 50, № 3, pp. 1-20 (2018). DOI: 10.1615/JAutomatInfScien.v50.i3.10.
7. Rothstein A. Intellectual technologies of identification: fuzzy sets, genetic
algorithms, neural nets. Vinnitsa: UNIVERSUM, 320 p. (1999)
8. Zadeh L.A. The concept of a linguistic variable and its application to approximate
reasoning – I // Information Sciences, 8(3), pp.199-249 (1975)
9. Zimmerman H.-J. Fuzzy Sets Theory and Its Applications, 4th ed. Boston: Kluwer
Acad. Publ., 514 р. (2001)
10. Borisov V.V., Kruglov V.V., Fedulov A.S. Fuzzy models and networks. Moscow:
Hotline-Telecom, 284 p. (2015) [in Russian]
11. Shor, N.Z. Nondifferentiable optimization and polynomial problems. Boston;
Dordrecht; London: Kluwer Acad. Publ., 412 p. (1998)
12. Shor N.Z. Minimization methods for non-differentiable functions // Springer
series, Computational mathematics. Berlin: Springer-Verlag, vol. 3, 162 p. (1985)
13. Atamtürk 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, vol. 1, pp. 247-259 (1995)
14. Aurenhammer F., Klein R., Lee D.-T. Voronoi Diagrams and Delaunay
Triangulations. World Scientific Pub Co Inc, 337 p. (2013)
15. Bakolas E., Tsiotras P. The Zermelo-Voronoi diagram: A dynamic partition
problem // Automatica, 46 (12), pp. 2059-2067 (2010)
16. Balzer M. Capacity-constrained Voronoi diagrams in continuous spaces // The
International Symposium on Voronoi Diagrams in Science and Engineering
(2009)
17. Jooyandeh Mohammadreza, Mohades Ali, Mirzakhah Maryam. Uncertain
Voronoi diagram // Information Processing Letters, 109 (13), 709-712 (2009)
18. Ledoux H., Christopher M. Gold modelling three-dimensional geoscientific fields
with the Voronoi diagram and its dual // International Journal of Geographical
Information Science, 22 (5), pp. 547-574 (2008)
19. Nishida T., Sugihara K., Kimura M. Stable marker-particle method for the
Voronoi diagram in a flow field // Journal of Computational and Applied
Mathematics, 202 (2), pp. 377-391 (2007).
20. Okabe A., Boots B, Sugihara K., Chiu S.N. Spatial Tessellations: Concepts and
Applications of Voronoi Diagrams // West Sussex, England: John Wiley and Sons
Ltd, second ed., 696 p. (2000)