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

Dragos Arotaritei

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

Full Text:

PDF

References


Fortune, S. (1887); A sweep algorithm for Voronoi Diagrams, Algoritmica, 2:153-174.
http://dx.doi.org/10.1007/BF01840357

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

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

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.
http://dx.doi.org/10.1007/BF02187890

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.

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

Aurenhammer, F.; Edelsbrunner, H.; An optimal algorithm for constructing the weighted Voronoi diagram in the plane, Pattern Recognition, 17(2): 251-257.
http://dx.doi.org/10.1016/0031-3203(84)90064-5

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.

Buckley, J.J. ; Eslami, E. (1997); Fuzzy plane geometry II: Circles and polygons,Fuzzy Sets and Systems, 87:79-85.
http://dx.doi.org/10.1016/S0165-0114(96)00295-3

Jooyandeh, M.; Mohades, A.; Mirzakah, M. (2009); Uncertain Voronoi Diagram, Information Processing Letters, 109:709-712.
http://dx.doi.org/10.1016/j.ipl.2009.03.007

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.

Chaudhuri, B. B. (1991); Some shape definitions in fuzzy geometry of space, Pattern Recognition Letters, 12: 531-535.
http://dx.doi.org/10.1016/0167-8655(91)90113-Z

Goetschel, R.; Voxman, W. (1986); Elementary fuzzy calculus, Fuzzy sets and systems, 18:31-43.
http://dx.doi.org/10.1016/0165-0114(86)90026-6

Takahashi, O.; Schilling, R.J. (1989); Motion Planning in Plane Using Generalized Voronoi Diagrams, IEEE Transactions on Robotics and Automation, 5(2):143-150.
http://dx.doi.org/10.1109/70.88035

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.

Kaufmann, A.; Gupta, M.M. (1984); Introduction to Fuzzy Arithmetic: Theory and Applications, an Nostrand Reinhold Company, NY.

Chakraborty, C.; Chakraborty, D. (2006); A theoretical development on a fuzzy distance measure for fuzzy numbers, Mathematical and Computer Modelling, 43:254-261.
http://dx.doi.org/10.1016/j.mcm.2005.09.025

Grzegorzewski, P. (1998); Metrics and orders in space of fuzzy numbers, Fuzzy Sets and Systems, 97:83-94.
http://dx.doi.org/10.1016/S0165-0114(96)00322-3

Woxman, W. (1998); Some remarks on distance between fuzzy numbers, Fuzzy Sets and Systems, 100:353-365.
http://dx.doi.org/10.1016/S0165-0114(97)00090-0




DOI: https://doi.org/10.15837/ijccc.2014.4.31



Copyright (c) 2017 Dragos Arotaritei

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

CC-BY-NC  License for Website User

Articles published in IJCCC user license are protected by copyright.

Users can access, download, copy, translate the IJCCC articles for non-commercial purposes provided that users, but cannot redistribute, display or adapt:

  • Cite the article using an appropriate bibliographic citation: author(s), article title, journal, volume, issue, page numbers, year of publication, DOI, and the link to the definitive published version on IJCCC website;
  • Maintain the integrity of the IJCCC article;
  • Retain the copyright notices and links to these terms and conditions so it is clear to other users what can and what cannot be done with the  article;
  • Ensure that, for any content in the IJCCC article that is identified as belonging to a third party, any re-use complies with the copyright policies of that third party;
  • Any translations must prominently display the statement: "This is an unofficial translation of an article that appeared in IJCCC. Agora University  has not endorsed this translation."

This is a non commercial license where the use of published articles for commercial purposes is forbiden. 

Commercial purposes include: 

  • Copying or downloading IJCCC articles, or linking to such postings, for further redistribution, sale or licensing, for a fee;
  • Copying, downloading or posting by a site or service that incorporates advertising with such content;
  • The inclusion or incorporation of article content in other works or services (other than normal quotations with an appropriate citation) that is then available for sale or licensing, for a fee;
  • Use of IJCCC articles or article content (other than normal quotations with appropriate citation) by for-profit organizations for promotional purposes, whether for a fee or otherwise;
  • Use for the purposes of monetary reward by means of sale, resale, license, loan, transfer or other form of commercial exploitation;

    The licensor cannot revoke these freedoms as long as you follow the license terms.

[End of CC-BY-NC  License for Website User]


INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL (IJCCC), With Emphasis on the Integration of Three Technologies (C & C & C),  ISSN 1841-9836.

IJCCC was founded in 2006,  at Agora University, by  Ioan DZITAC (Editor-in-Chief),  Florin Gheorghe FILIP (Editor-in-Chief), and  Misu-Jan MANOLESCU (Managing Editor).

Ethics: This journal is a member of, and subscribes to the principles of, the Committee on Publication Ethics (COPE).

Ioan  DZITAC (Editor-in-Chief) at COPE European Seminar, Bruxelles, 2015:

IJCCC is covered/indexed/abstracted in Science Citation Index Expanded (since vol.1(S),  2006); JCR2018: IF=1.585..

IJCCC is indexed in Scopus from 2008 (CiteScore2018 = 1.56):

Nomination by Elsevier for Journal Excellence Award Romania 2015 (SNIP2014 = 1.029): Elsevier/ Scopus

IJCCC was nominated by Elsevier for Journal Excellence Award - "Scopus Awards Romania 2015" (SNIP2014 = 1.029).

IJCCC is in Top 3 of 157 Romanian journals indexed by Scopus (in all fields) and No.1 in Computer Science field by Elsevier/ Scopus.

 

 Impact Factor in JCR2018 (Clarivate Analytics/SCI Expanded/ISI Web of Science): IF=1.585 (Q3). Scopus: CiteScore2018=1.56 (Q2); Editors-in-Chief: Ioan DZITAC & Florin Gheorghe FILIP.