INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL
ISSN 1841-9836, 9(4):389-396, August, 2014.

A Method to Construct Approximate Fuzzy Voronoi Diagram for
Fuzzy Numbers of Dimension Two

D. Arotaritei

Dragos Arotaritei
"Grigore T. Popa" University of Medicine and Pharmacy
Romania, 700115 Iasi, Str. Universitatii, 16
E-mail: dragos.arotaritei@umfiasi.ro

Abstract: In this paper, we propose an approximate "fuzzy Voronoi" diagram
(FVD)for fuzzy numbers of dimension two (FNDT) by designing an extension of
crisp Voronoi diagram for fuzzy numbers. The fuzzy Voronoi sites are defined as
fuzzy numbers of dimension two. In this approach, the fuzzy numbers have a convex
continuous differentiable shape. The proposed algorithm has two stages: in the first
stage we use the Fortune’s algorithm in order to construct a "fuzzy Voronoi" diagram
for membership values of FNDTs that are equal to 1. In the second stage, we propose
a new algorithm based on the Euclidean distance between two fuzzy numbers in order
to construct the approximate "fuzzy Voronoi" diagram for values of the membership
of FNDTs that are smaller than 1. The experimental results are presented for a
particular shape, the fuzzy ellipse numbers.
Keywords: approximated fuzzy Voronoi diagram, fuzzy numbers of dimension two,
computational geometry, fuzzy arithmetic, bisector median, path planning.

1 Introduction

Many studies have been made relating to Voronoi diagram and its application [1]. Usually,
the main algorithms deal with exact Voronoi diagram. Only few of them deal with approximated
Voronoi diagram. In some of paper, 2D objects has been taken into account in order to construct
Voronoi diagram. An algorithm to construct Voronoi diagram for convex sites is proposed in [2].
The authors start with the post- office problem where the main question is how to process a set
of sites in the plane in order to find the closest site to a query point. The study in [2] treats
points as disjoint convex polygons.

In [3] the authors proposed Voronoi diagrams of ellipses using an incremental algorithm that
constructs also the exact Delauny graph. A distance from a point to an ellipse is defined to be
the minimum Euclidean distance to the boundary of the ellipse with negative value in case the
point is inside the ellipse.

Most of the papers treat the problem of disjoint objects. In some papers, the objects can
intersect [4] or one object can be inside another object [4]. In the latter case, the circles can in-
tersect each other and circles can contain other circles [4]. In [5] the authors used an incremental
algorithm in order to construct Voronoi diagrams for convex objects. A polynomial approxima-
tion of the curves is suggested. An algorithm that computes an approximate version of Voronoi
diagram is introduced in [6]. The cells in these approximated diagrams are cubes or difference of
two cubes. Other papers deal with weighted Voronoi diagrams [7] using the Euclidean distance
functions. Each point p from a given set P of points in the plane has an associated weight that
expresses the level of influence over this neighborhood.

Fuzzy objects are an important part in the fuzzy set theory. 1-D fuzzy sets have been extended
to fuzzy plane and fuzzy plane geometry (circles and polygons) in [9]. Only very few papers deal
with fuzzy Voronoi diagram. In ( [10]- [11]) the authors proposed an algorithm that deals with
fuzzy objects in fuzzy Voronoi diagrams. The "Fuzzy Voronoi" diagram is an extension of the
Voronoi diagram based on Fortune’s algorithm for crisp cases. The "Fuzzy Voronoi" diagram

Copyright © 2006-2014 by CCC Publications



390 D. Arotaritei

has been extended for a set of fuzzy circles, rather than fuzzy points, of the same radius. The
authors proved that the boundaries of this diagram are constructed by intersecting a number of
hyperbolae and they proposed an algorithm that computes the exact formula [11]. The geometric
approach is presented in [12]. The authors define the basic fuzzy geometric shapes (point, line,
circle, ellipse and polygon) using the 2-D support space on the level of fuzzy set. A fuzzy measure
for trapezoidal fuzzy number is proposed in [13].

Optimal Path Planning for Mobile Robot Navigation is an important area of research in
computer science. Usually, obstacles are approximated by rectangular or circular cylinders and
Voronoi diagram can be an effective solution [14]. An interesting approach is optimal path
planning in an uncertain (fuzzy) environment and 3D space that conduct to idea of fuzzy Voronoi
diagram. Fuzzy solution can be very effective for various problems [15].

We present a different algorithm that computes an approximated fuzzy Voronoi diagram for
fuzzy numbers of dimension two. It is possible to extend the proposed algorithm to n-dimensional
fuzzy numbers using α-cuts.

2 Fuzzy Numbers of Dimension Two

Before we proceed to the main results described in this paper we make a short review of the
crisp Voronoi diagram [1] and FNDT [16]. Some proposal for fuzzy distance are investigated
by some authors ( [17]- [19]). We will use Euclidean distance in fuzzy workspace and some of
notations adapted from [11] for Voronoi cell and Voronoi diagram.

LetP be a discrete subset in the metric space X. The Voronoi cell V (p) is defined as the set
of all points x in X that have the distance to p lower or equal to the distance from x to other
points q in P [11].

V (p) = {x ∈ X|∀q ∈ P, d(x, p) ≤ d(x, q)} (1)

The Voronoi diagram of P is the set of all Voronoi cells denoted by V (p). The points p are
named Voronoi sites of the set P ( [10]- [11]). A fuzzy numbers of dimension n can be defined
according to ( [9], [16]). Let’s consider a fuzzy graph G ⊂ R × R... × R, a functional relation
in Rn having the membership function µG(x1, x2, ..., xn) ∈ Rn. We define an n-dimensional
fuzzy number F[A]n as any non-empty convex fuzzy subset of G ∈ Rn that meets the following
conditions [16]:

• A is a normal fuzzy set, i.e. there is an x0 ∈ Rn, µG(x0) = 1;

• A is a convex set, that is membership function is convex hypersurface, i.e. µA(αx + (1 −
α)y) ≥ min(µA(x), µA(y)), α ∈ (0, 1];

• The membership function is a convex hypersurface that for ∀a ∈ R, there is µA(x) = a.

In particular, for n=2 we have fuzzy numbers of dimension two (FNDT), as they are defined in
( [9], [16]). A general shape is shown in Fig. 1a. In Fig. b we showed the cut of this surface (top
view) for a level α ∈ (0, 1].

The Fuzzy Voronoi diagram involves computing distances in fuzzy spaces. The results of
calculus depend of the metrics used for the fuzzy space.An important point is the selection of
the shape of FNDT, derivable in all the points or not: convex polygon, rectangular, square,
circle, ellipse or closed curves. In our approach, a continuous convex closed curve of FNDT is
considered. The circle or ellipsis is a particular case.

Various metrics in F̃(ℜ) have been proposed in the literature, most of them based on the
Hausdorff distance ( [18]- [19]). Other authors proposed definitions for measures in the Euclidean



A Method to Construct Approximate Fuzzy Voronoi Diagram for Fuzzy Numbers of Dimension
Two 391

Figure 1: (a) A fuzzy number of dimension 2; (b) Top view of α-cut of FNDT (general case)

space, function that capture more information about vagueness, α-cut that transform fuzzy
number into an interval number and distance index based on centroid of fuzzy number. The
α-level set Aα of a fuzzy number is a non fuzzy set defined by:

Aα = {x ∈ ℜ|µ(x) ≥ α}, µA(x) = sup
a∈(0,1]

{α · GAα(x)} (2)

where GAα(x) is the characteristic of the function Aα.

3 Approximated Fuzzy Voronoi Diagram (AFVD) for Fuzzy Num-
bers of Dimension Two

In the next paragraphs we define the FVD for a set of sites that are fuzzy numbers of
dimension two. Let p̃ be a subset of ℜ2, which is constructed from fuzzy numbers of dimension
two and let p̃ ∈ P̃ be a FNDT. A fuzzy Voronoi cell of p̃ is defined, in a similar manner as in [11],
by Ṽ (p̃):

Ṽ (p̃) = {(x, µp̃(p̃))|∀q̃ ∈ P̃, d(x, p) ≤ d(x, q)} (3)

We note p = (px, py) and q = (qx, qy) two crisp points that belong to a FNDT at α-cut level.
We omitted α from the following formulae in order to simplify the notations. The Euclidean
distance between two points p and q that belong to a FNDT at α-cut level is given by:

dE(p, q) =
√
(px − qx)2 + (py − qy)2 (4)

This definition is consistent with the results obtained in the particular degenerated case when
FNDT become a single point or when α = 1. Let us consider two FNDT ellipse shapes not
necessary equal. Each level of the α-cuts level will produce two ellipses in the same plane. The
fuzzy Voronoi diagram for n FNDT is the union of Voronoi diagrams of fuzzy α-cuts for all n
FNDT. Each α-cut of FNDT become a set of ellipses for which a Voronoi diagram is required.

It is easy to demonstrate that given two disjoint continuous convex closed curves A and B,
for any two points inside of continuous convex closed curves, the bisector median of these two
points are bordered by other two bisector median of two points situated on the contour of the
curves. A conclusion of this assertion is that to construct the bisector median of all the points
on surface of two continuous convex closed curves it is enough to construct the bisector median
for all the points on the contour of the curve that is the border of the bisector median for all the
points.



392 D. Arotaritei

Figure 2: (a) The construction of the bisector median for two points located on the FNDT and
the asymptotes of the FVD; (b) The construction of APVD for first curve

For each α-cut, we can compute the fuzzy Voronoi diagram using only the contour of the
curve from FNDT obtained by this α-cut. In what follows, we will denote by hk ∈[0,1) the α-cut
level of index k.

The starting point for our approach is the calculus of bisector median for two points, one of
them situated on the first curve and the second one situated on the second curve. Let’s denote
by X1(x1, y1) and X2(x2, y2) these two points. The equation of the bisector median is given by
a line, perpendicular on the middle of the segment X1X2. If the slope of the line X1X2 is m,the
slope of the bisector median of X1X2 will be m′ = −1/m = (x2 − x1)/(y2 − y1). The equation
bisector median (BM) is a line that pass by the point M(xm, ym), the middle of the segment
X1X2 and it has the slope m′. After few manipulations, the BMs equation si given by:

y = −
x2 − x1
y2 − y1

· x +
x22 + y

2
2 − x

2
1 − y

2
1

2 · (y2 − y1)
(5)

The fuzzy Voronoi diagram for two FNDT consists from all the bisector medians for all the points
situated on the two closed curves. The asymptotes for the envelopes of all bisector medians is
given by the bisector median of internal tangents of the two closed convex curves. If we apply
counterclockwise rotation and translation for any point with φ angle in Euclidean space, for any
two ellipses we have simplified parametric equations of two ellipses (as in Fig. 2(a) and Fig.
2(b)).

Let’s consider two convex closed curve that after eventually rotation and translation looks
like in Fig. 2(a). The origin of axis is located in the center point of the first unimodal FNDT
and his center point of the second unimodal FNDT is located on the axis 0X (Fig 2(a)).

We consider two points situated on this curves X1(x1, y1) and X2(x2, y2) as in Fig. 2b. The
bisector median of these points will be given by formula (5). Let’s consider a line that pass
in the point C1(0, 0), with m2 incrementally from point TL2 and TL1 arbitrary chosen on the
asymptotic limits for fuzzy Voronoi Diagram S1 and S2. The two lines intersect in the point
P(xp, yp) given by the solution of the system:{

yp = m1xp + n1

yp = m2xp + n2
(6)

{
m1 = −(x2 − x1)/(y2 − y1), n1 = (x22 + y

2
2 − x

2
1 − y

2
1)/(2 · (y2 − y1))

m2 = const., n2 = 0
(7)



A Method to Construct Approximate Fuzzy Voronoi Diagram for Fuzzy Numbers of Dimension
Two 393


xp =

x22+y
2
2−x

2
1−y

2
1

2·(x2−x1+m2·(y2−y1))

yp = m2xp
(8)

If m1 ̸= m2, the two line intersect in the point P(xp, yp), where xp = (n1 − n2)/(m1 − m2) and
yp = m1((n1 − n2)/(m1 − m2)) + n1. In the case m1 = m2, the two lines are parallel, so no
intersection point exists. In our algorithm we simply skip this situation and we go to the next
increment.

Let’s consider the bisector median for points C1 and C2. This crisp Voronoi diagram for two
points C1 and C2 split conventionally the plane in two halves, left (where first curve is located)
and right (where the curve is located). The envelope of the fuzzy Voronoi Diagram for left
half-plane is given by the minimum of distance between points P and C1. For a given m1, this
distance is the intersection of the line R (Fig. 2(b)) and one of the bisector median for all the
lines given by formula (5). The minimum of distance is given by:

Dm = d
2(C1, P) = d

2
m = x

2
p + y

2
p = m

2
1 · x

2
p (9)

The function Dm reach the minimum when x2p reach the minimum, that is we must find (x1, y1)
and (x2, y2) for which this minimum is obtained. If the curves are given by parametric equations,
this mean that we must find the pair (t1, t2) for which Dm = F(x1(t1), y1(t1), x2(t2), y2(t2)) =
G(t1, t2), t1 ∈ ∠(T11, a, T12), t2 ∈ ∠(T21, c, T22) reach the minimum for a given m2. For each
m2j ∈ [mmin, mmax], j = 1, ...n we will find an Pj. The union of all the Pj will give the left
envelope of the AFVD for these two FNDT at hk level of α-cut. The envelope is asymptotic
limited by the bisector median of the internal tangents.

FVleft =

n∪
j=1

Pj (10)

For the right side, the formulas (6)-(9) are a bit changed, taking into account the equation of
the line R that must pass in the point C2(XC2, 0). After few calculations, the formulas become:

xp =
x22+y

2
2−x

2
1−y

2
1−q·(y2−y1)

2·(x2−x1+m2·(y2−y1))
, q = 2 · m2 · XC2 = const.

yp = m2xp + n2, n2 = −m2 · XC2
(11)

Dm = d
2(CA2, P) = d

2
m (12)

d2m = (xp − XC2)
2 + y2p = (1 + m

2
2) · x

2
p + 2 · (m2n2 − SC2) · xp + XC2

2 + n22) (13)

AFVD use numerical methods to find the minimum of function given by formulas (7)-(13). Let’s
suppose that we have the equation of curves given by parametric formula. We can convert
the equation of curves into parametric formulas. The quadratic form (circle, ellipse) can be
easily converted to parametric form. We taken into account two options. The first one use a
minimization with constrains of the function Dm as a function of two parameters in order to find
(t1, t2) and so one (xp, yp).

mint1,t2F(t1, t2) such that t1,min ≤ t1,max, t2,min ≤ t2 ≤ t2,max (14)

It is a problem o constrained nonlinear optimization that can be solved by many methods:
interior-point, SQP, active-set, trust-region-reflective. We chosen to use function fmincon imple-
mented in MATLAB toolbox.



394 D. Arotaritei

The second option is possible in the case of twice differentiable curves. We can find the
extremum of the function F(t1, t2) by calculating the stationary points using first partial deriva-
tive and thereafter by select the points that are local minimum using the second derivative. The
saddle and the maximum points are eliminated.

Both numerical solutions have a problem: how to choose the initial point in order find the
global minimum. The surface of equations (13)-(11) can have many local minima, so we must
start with initial solution close enough to global minimum. In order to overcome this situation,
we propose to use a brute-force algorithm (BFI ) to find the initial points. We split the domain of
ti, i=1,2 in ni parts. For each combination (tij, tik) we find a bisector median and a intersection
points. In total we will have maximum n1 ∗ n2 lines that intersect the line R. Using formula
(14), the pairs (t10, t20) for which the minimum of F(t1, t2) is obtained is the starting point for
minimization in the next refinement stage.

The same reasoning is used for the second curve that have the center C2(XC2, 0). After
both envelopes have been found, we rotate and translate the curves in order to come in initial
position. In our experiments we used the first method and the ’trust-region-reflective’ algorithm.

4 Algorithm for Approximated Fuzzy Voronoi Diagram and Ex-
perimental Results

We can summarize the algorithm for APVD as follow.

Step 1: Construct the crisp Voronoi diagram for crisp points that are the centers of convex
closed curves (Fortune’s algorithm)P.

Step 2: For each level hk of α-cuts do the two following steps..
Step 3: For each Voronoi cell that includes a convex closed curve Ai, construct the fuzzy border

generated by all adjacent crisp Voronoi cells. The fuzzy border is generated by AFVD
described previously.

Step 4: Calculate the intersection of the fuzzy borders and apply the norm max for all fuzzy
points.

Step 5: If hk ̸= 0.0, go to Step 2, else Stop the algorithm.

In our experimental results we used ellipses given in a parametric form. It is easy to transform
the parametric form into quadratic form, and reverse. The experimental results, AFVD for six
ellipses, are presented in Fig. 3a and Fig. 3b. In Fig. 3b, the solid line inside the grey area
represents the crisp Voronoi diagram for centers Ci of closed curves (ellipses).

Unbounded cells have at infinite the limit determined by internal tangent of adjacent cells
corresponding to crisp Voronoi cells of the centers of closed curves (ellipses).

Computational time for Crisp Voronoi (Fortune’s algorithm) is given by the known result
O(n log n). Our approach considers a less efficient algorithm, based on construction of bisector
lines, for which the computational time is O(n2 log n).

5 Conclusions and Future Works

In this paper, we introduced Approximated fuzzy Voronoi diagram for fuzzy numbers of
dimension two. We developed an original algorithm for computing fuzzy Voronoi diagram for
fuzzy numbers of dimension two with closed convex derivable curve shape. We used α-cuts in
order to develop the diagram and the boundaries of Voronoi edges of fuzzy cells.



A Method to Construct Approximate Fuzzy Voronoi Diagram for Fuzzy Numbers of Dimension
Two 395

Figure 3: (a)The maximum norm for all fuzzy points inside a fuzzy Voronoi cell (CVDE: Crisp
Voronoi Diagram-Edges); (b)AFVD for six ellipses

We considered not only the contour of the fuzzy numbers of dimension two at h level of α-cuts
but also points inside this area. The same dimension for all the fuzzy object is a particular case
of the presented algorithm. The fuzzy numbers have the same size but different sizes are taken
into account.

The experimental results presented the fuzzy Voronoi diagram for FNDT not only for two
sites but also for six sites with applicability and algorithm extension to n sites.

Bibliography

[1] Fortune, S. (1887); A sweep algorithm for Voronoi Diagrams, Algoritmica, 2:153-174.

[2] Mcallisterm, M.; Kirkpatrick, D.; Snoeyink, J. (1996); A compact piecewise-linear Voronoi
diagram for convex sites in the plane, Discrete Comput. Geom., 15-73.

[3] Karavelas, M.; Yvinec, M. (2003); Voronoi diagram of convex objects in the plane, In Proc.
Europ. Symp. Algorithms, LNCS Springer, 337-348.

[4] Yap, C. K. (1987); O(n log n) Algorithm for the Voronoi Diagram of a Set of Simple Curve
Segments, Discrete Comput. Geom., 2:365-393.

[5] Arya, S.; Malamatos, T. (2002); Linear-size approximate Voronoi diagrams, In: 13th Annual
ACM-SIAM Symp. on Discrete algorithms, Society for Industrial and Applied Mathematics,
147-155.

[6] Emiris, I.; Hemmer, M.; Tsigaridas, E.; Tzoumas, G. (2008); Voronoi diagram of ellipses:
CGAL-based implementation, ACS-TR-363603-01 Technical Report, University of Gronin-
gen.

[7] Aurenhammer, F.; Edelsbrunner, H.; An optimal algorithm for constructing the weighted
Voronoi diagram in the plane, Pattern Recognition, 17(2): 251-257.



396 D. Arotaritei

[8] Burnikel, C.; Mehlhorn, K.; Schirra, S. (1994); How to Compute Voronoi Diagram of Line
Segments: Theoretical and Experimental Results, In Proc. 2nd Annual Symposium, Lecture
Notes of Computer Science, 855:227-237.

[9] Buckley, J.J. ; Eslami, E. (1997); Fuzzy plane geometry II: Circles and polygons,Fuzzy Sets
and Systems, 87:79-85.

[10] Jooyandeh, M.; Mohades, A.; Mirzakah, M. (2009); Uncertain Voronoi Diagram, Informa-
tion Processing Letters, 109:709-712.

[11] Jooyandeh, M.; Khorasani, A.M. (2009); Fuzzy Voronoi Diagram, Advances in Computer
Science and Engineering, 13th International CSI Computer Conference, CSICC 2008, 6:82-89.

[12] Chaudhuri, B. B. (1991); Some shape definitions in fuzzy geometry of space, Pattern Recog-
nition Letters, 12: 531-535.

[13] Goetschel, R.; Voxman, W. (1986); Elementary fuzzy calculus, Fuzzy sets and systems,
18:31-43.

[14] Takahashi, O.; Schilling, R.J. (1989); Motion Planning in Plane Using Generalized Voronoi
Diagrams, IEEE Transactions on Robotics and Automation, 5(2):143-150.

[15] Razavi, S.H.; H. Amoozad, H.; Zavadskas, E.K. ; Hashemi, S.S. (2013); A Fuzzy Data
Envelopment Analysis Approach based on Parametric Programming, International Journal
of Computers Communications & Control, ISSN 1841-9836, 8(4):594-607.

[16] Kaufmann, A.; Gupta, M.M. (1984); Introduction to Fuzzy Arithmetic: Theory and Appli-
cations, an Nostrand Reinhold Company, NY.

[17] Chakraborty, C.; Chakraborty, D. (2006); A theoretical development on a fuzzy distance
measure for fuzzy numbers, Mathematical and Computer Modelling, 43:254-261.

[18] Grzegorzewski, P. (1998); Metrics and orders in space of fuzzy numbers, Fuzzy Sets and
Systems, 97:83-94.

[19] Woxman, W. (1998); Some remarks on distance between fuzzy numbers, Fuzzy Sets and
Systems, 100:353-365.