article

Uncertain Voronoi diagram

Authors:

Mohammadreza Jooyandeh,

Ali Mohades,

Maryam MirzakhahAuthors Info & Claims

Information Processing Letters, Volume 109, Issue 13

Pages 709 - 712

https://doi.org/10.1016/j.ipl.2009.03.007

Published: 01 June 2009 Publication History

Abstract

In this paper, we introduce the fuzzy Voronoi diagram as an extension of the Voronoi diagram. We assume Voronoi sites to be fuzzy points and then define the Voronoi diagram for this kind of sites, then we provide an algorithm for computing this diagram based on Fortune's algorithm which costs O(nlogn) time. Also we introduce the fuzzy Voronoi diagram for a set of fuzzy circles, rather than fuzzy points, of the same radius. We prove that the boundary of this diagram is formed by the intersection of some hyperbolae, and finally we provide an O(n^3logn)-time algorithm to compute the boundary.

References

[1]

Fortune, S., A sweepline algorithm for Voronoi diagrams. Algorithmica. v2. 153-174.

Google Scholar

[2]

The Wolfram Research, Mathematica, version 6.0.2, 2008

Google Scholar

[3]

Kim, D.S., Kim, D. and Sugihara, K., Voronoi diagram of a circle set from Voronoi diagram of a point set. Comput. Aided Geom. Des. v18. 563-585.

Crossref

Google Scholar

[4]

Kavka, C. and Schoenauer, M., Evolution of Voronoi-based fuzzy controllers. In: Yao, E.A. (Ed.), Lecture Notes in Computer Science, pp. 541-550.

Crossref

Google Scholar

Cited By

View all

Chen JDames P(2023)The Convex Uncertain Voronoi Diagram for Safe Multi-Robot Multi-Target Tracking Under Localization UncertaintyJournal of Intelligent and Robotic Systems10.1007/s10846-023-01986-0109:4Online publication date: 22-Nov-2023
https://dl.acm.org/doi/10.1007/s10846-023-01986-0
Chen JDames P(2020)Collision-Free Distributed Multi-Target Tracking Using Teams of Mobile Robots with Localization Uncertainty2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS45743.2020.9341126(6968-6974)Online publication date: 24-Oct-2020
https://dl.acm.org/doi/10.1109/IROS45743.2020.9341126
Agarwal PEfrat ASankararaman SZhang W(2017)Nearest-Neighbor Searching Under Uncertainty IDiscrete & Computational Geometry10.1007/s00454-017-9903-x58:3(705-745)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s00454-017-9903-x
Show More Cited By

Uncertain Voronoi diagram
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Fuzzy Voronoi diagram for disjoint fuzzy numbers of dimension two

In this paper, we introduce “fuzzy Voronoi” diagrams for fuzzy numbers of dimension two FNDT by extension of crisp Voronoi diagrams for fuzzy numbers. The fuzzy Voronoi sites are defined as fuzzy numbers of dimension two. All the operations are defined ...
Efficient computation of 3d clipped voronoi diagram
GMP'10: Proceedings of the 6th international conference on Advances in Geometric Modeling and Processing

The Voronoi diagram is a fundamental geometry structure widely used in various fields, especially in computer graphics and geometry computing. For a set of points in a compact 3D domain (i.e. a finite 3D volume), some Voronoi cells of their Voronoi ...
Voronoi-Delaunay duality and Delaunay meshes
SPM '07: Proceedings of the 2007 ACM symposium on Solid and physical modeling

We define a Delaunay mesh to be a manifold triangle mesh whose edges form an intrinsic Delaunay triangulation or iDT of its vertices, where the triangulated domain is the piecewise flat mesh surface. We show that meshes constructed from a smooth surface ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information Processing Letters Volume 109, Issue 13

June, 2009

117 pages

ISSN:0020-0190

Issue’s Table of Contents

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 01 June 2009

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chen JDames P(2023)The Convex Uncertain Voronoi Diagram for Safe Multi-Robot Multi-Target Tracking Under Localization UncertaintyJournal of Intelligent and Robotic Systems10.1007/s10846-023-01986-0109:4Online publication date: 22-Nov-2023
https://dl.acm.org/doi/10.1007/s10846-023-01986-0
Chen JDames P(2020)Collision-Free Distributed Multi-Target Tracking Using Teams of Mobile Robots with Localization Uncertainty2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS45743.2020.9341126(6968-6974)Online publication date: 24-Oct-2020
https://dl.acm.org/doi/10.1109/IROS45743.2020.9341126
Agarwal PEfrat ASankararaman SZhang W(2017)Nearest-Neighbor Searching Under Uncertainty IDiscrete & Computational Geometry10.1007/s00454-017-9903-x58:3(705-745)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s00454-017-9903-x
Ghosh DChakraborty D(2016)Analytical fuzzy plane geometry IIIFuzzy Sets and Systems10.1016/j.fss.2014.10.018283:C(83-107)Online publication date: 15-Jan-2016
https://dl.acm.org/doi/10.1016/j.fss.2014.10.018
Sivignon I(2016)Representation of Imprecise Digital ObjectsProceedings of the 19th IAPR International Conference on Discrete Geometry for Computer Imagery - Volume 964710.1007/978-3-319-32360-2_31(401-414)Online publication date: 18-Apr-2016
https://dl.acm.org/doi/10.1007/978-3-319-32360-2_31
Li GLi LLi JLi Y(2015)Network Voronoi Diagram on uncertain objects for nearest neighbor queriesInformation Sciences: an International Journal10.1016/j.ins.2014.12.050301:C(241-261)Online publication date: 20-Apr-2015
https://dl.acm.org/doi/10.1016/j.ins.2014.12.050
Kiseleva EKoriashkina L(2015)Theory of Continuous Optimal Set Partitioning Problems as a Universal Mathematical Formalism for Constructing Voronoi Diagrams and Their Generalizations. I. Theoretical FoundationsCybernetics and Systems Analysis10.1007/s10559-015-9725-x51:3(325-335)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1007/s10559-015-9725-x
Arotaritei DIonescu F(2014)Fuzzy Voronoi diagram for disjoint fuzzy numbers of dimension twoJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.5555/2596417.259643526:3(1253-1262)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.5555/2596417.2596435
Xie XCheng RYiu MSun LChen J(2013)UV-diagramThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-012-0290-x22:3(319-344)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s00778-012-0290-x
Agarwal PEfrat ASankararaman SZhang WLenzerini MBenedikt M(2012)Nearest-neighbor searching under uncertaintyProceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems10.1145/2213556.2213588(225-236)Online publication date: 21-May-2012
https://dl.acm.org/doi/10.1145/2213556.2213588

Abstract

References

Cited By

Recommendations

Fuzzy Voronoi diagram for disjoint fuzzy numbers of dimension two

Efficient computation of 3d clipped voronoi diagram

Voronoi-Delaunay duality and Delaunay meshes

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations