Voronoi-Diagram-Simulation

The purpose of this project is to build the Voronoi cell that corresponds to a point at the origin using a set of points that are evenly distributed over a plane.

References

• Aurenhammer, F., & Edelsbrunner, H. (1984). An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition, 17(2), 251–257.

• Candeloro, M., Lekkas, A. M., & Sorensen, A. J. (2017). A Voronoi-diagram-based dynamic path-planning system for underactuated marine vessels. Control Engineering Practice, 61, 41–54.

• Okabe, A., Boots, B., Sugihara, K., & Chiu, S. N. (2009). Spatial tessellations: Concepts and applications of Voronoi diagrams. John Wiley & Sons.

• F. Aurenhammer, H. Edelsbrunner, "An optimal algorithm for constructing the weighted Voronoi diagram in the plane," Pattern Recognition, Vol. 17, no. 2, pp. 251–257, 1984. DOI: 10.1016/0031-3203(84)90064-5.

• F. Aurenhammer, R. Klein, D.-T. Lee, "Voronoi diagrams and Delaunay triangulations," World Scientific Publishing, Singapore, 2013.

• M. Candeloro, A. M. Lekkas, A. J. Sorensen, "A Voronoi-diagram-based dynamic path-planning system for underactuated marine vessels," Control Engineering Practice, Vol. 61, pp. 41–54, 2017. DOI: 10.1016/j.conengprac.2017.01.007.

• G. Cosquer, J. F. Hangouët, "Delimitation of land and sea boundaries: Geodetic and geometric bases," FIG Working Week 2003, Paris, France, April 13–17, 2003.

• P. Dong, "Generating and updating multiplicatively weighted Voronoi diagrams for point, line and polygon features in GIS," Computers & Geosciences, Vol. 34, no. 4, pp. 411–421, 2008.

• J. Gaździcki, "Systemy informacji przestrzennej," Państwowe Przedsiębiorstwo Wydawnictw Kartograficznych, Warszawa, 1990.

• M. Gavrilova (Ed.), "A Geometry-based approach to computational intelligence," Studies in Computational Intelligence, Vol. 158, Springer, 2008.

• M. Kratko, "Heorhij Woronyj – matematyk ukraiński i polski," http://voronuy.at.ua/publ/heorhij_woronyj_matematyk_ukrainski_i_polski/1-1-0-48, 2011.

• H. Ledoux, "Computing the 3D Voronoi diagram robustly: An easy explanation," Voronoi diagrams in science and engineering, ISVD ’07, 4th International Symposium, pp. 117–129, 2007.

• S. Lovacka, "The use of the Voronoi tessellation for purposes of service distribution districts delimitation (The example of the Prešov nodal region)," Folia Geographica, Vol. 12, pp. 163–171, 2008.

• A. Magnuszewski, "GIS w geografii fizycznej," Wydawnictwo Naukowe PWN, Warszawa, 1999.

• Mathworks Documentation, "Voronoi diagrams," https://www.mathworks.com/help/matlab/math/voronoi--diagrams.html.

• T. van der Putte, "Using the discrete 3D Voronoi diagram for the modelling of 3D continuous information in geosciences," Master Thesis, Utrecht University, 2009. http://www.gdmc.nl/publications/2009/3D_Voronoi_diagram.pdf.

• A. Okabe, B. Boots, K. Sugihara, S. N. Chiu, "Spatial tessellations: Concepts and applications of Voronoi diagrams," John Wiley & Sons, Chichester – New York, 2009.

• W. Pokojski, P. Pokojska, "Voronoi diagrams – inventor, method, applications," Polish Cartographical Review, Vol. 50, no. 3, pp. 141–150, 2018. DOI: 10.2478/pcr-2018-0009.

• A. Thiessen, "Precipitation averages for large areas," Monthly Weather Review, Vol. 39, no. 7, pp. 1082–1089, 1911.

• G. Voronoi, "Nouvelles applications des paramètres continus à la théorie de formes quadratiques," Journal für die Reine und Angewandte Mathematik, Vol. 134, pp. 198–287, 1908.

• S. Wang, J. Rong, Z. Yang, "Transit traffic analysis zone delineating method based on Thiessen polygon," Sustainability, Vol. 6, no. 4, pp. 1821–1832, 2014. DOI: 10.3390/su6041821.

• H. Wu, S. Takahashi, C. Lin, H. Yen, "Voronoi-based label placement for metro maps," 17th International Conference on Information Visualization, London, 2013, pp. 96–101. DOI: 10.1109/IV.2013.11.

• Y. Xu, X. H. Fan, K. G. Liu, L. Shi, B. Xu, F. M. Wang, J. P. Lin, "Applying and practicing of MATLAB programming for Voronoi tessellation," Advanced Materials Research, Vol. 706–708, pp. 391–394, 2013.

• Hacettepe Üniversitesi, "Week 8 Voronoi Diagrams," Hacettepe Üniversitesi, https://web.cs.hacettepe.edu.tr/lectures/lecture7.pdf.

• University of California, Irvine, "Voronoi Diagrams and Their Applications," University of California, Irvine, https://ics.uci.edu/geom/notes/Voronoi1.pdf.

• Brown University, "Introduction to Voronoi Diagrams," Brown University, https://cs.brown.edu/lectures/pdf/notes09.pdf.

• Tufts University, "1 Voronoi Diagrams 2 Definitions," Tufts University, http://www.cs.tufts.edu/comp/voronoi_handout.pdf.

• Purdue University, "Voronoi Diagrams (chapter 7)," Purdue Computer Science, https://www.cs.purdue.edu/homes/slides/vor.pdf.

• RKMVERI (Deemed University), "Voronoi Diagram," RKMVERI, https://cs.rkmvu.ac.in/~sghosh/subhas-lecture.pdf.

• J. D. Boissonnat, "Curved Voronoi diagrams," Archive ouverte HAL, https://hal.science/file/ecg-book-voronoi.pdf, 2007.

• A. Dobrin, "A review of properties and variations of Voronoi diagrams," Whitman College, https://www.whitman.edu/mathematics/dobrinat.pdf.

• Middle East Technical University, "Voronoi Diagrams and Delaunay Triangulation," METU, https://user.ceng.metu.edu.tr/Schedule/week9.pdf.

• University of Illinois Chicago, "Voronoi Diagrams," University of Illinois Chicago, http://homepages.math.uic.edu/~jan/mcs481.pdf.

• C. K. Li, "Voronoi Diagram," Chi-Kwong Li, https://cklixx.people.wm.edu/Voronoi-paper.pdf, 2020.

• P. Felkel, "Voronoi Diagram," CourseWare Wiki, https://cw.fel.cvut.cz/lectures/06-voronoi-split.pdf.

• Massachusetts Institute of Technology, "Lecture 7: Voronoi Diagrams," MIT, http://nms.lcs.mit.edu/~aklmiu/Lecture7.pdf, 2001.

• Instituto de Computação, "ALGORITHMS FOR CONSTRUCTING VORONOI DIAGRAMS," Instituto de Computação, https://www.ic.unicamp.br/~rezende/ensino/Voronoi.pdf.

• The University of New Mexico, "1 Voronoi Diagrams," The University of New Mexico, https://www.cs.unm.edu/~saia/classes/lec/Voronoi.pdf.

• D. M. Yana, "Efficient Computation of Clipped Voronoi Diagram for Optimal Mesh Generation," Microsoft, https://www.microsoft.com/uploads/2016/12/Voronoi.pdf, 2016.

• C. Wormser, "Generalized Voronoi Diagrams and Applications," HAL Thèses, https://theses.hal.science/document.pdf, 2008.

• Purdue University, "Voronoi diagrams and weighted complexes," Purdue University, https://www.cs.purdue.edu/course/Voronoi-CDS.pdf.

• DergiPark, "Path planning of autonomous mobile robots based on Voronoi Diagram and Ant Colony Algorithm," DergiPark, https://dergipark.org.tr/download/article-file.pdf.

• University of Arizona, "Properties of Voronoi Diagrams," University of Arizona, https://www2.cs.arizona.edu/Lecture7.prn.pdf.

• École Normale Supérieure de Lyon, "Convex Hulls, Voronoi Diagrams and Delaunay Triangulations," ENS Lyon, https://www.ens-lyon.fr/Arenaire/JDB-ens-lyon-I.pdf, 2010.

• O. Cheong, "Farthest-polygon Voronoi diagrams," Loria - Inria, https://members.loria.fr/fpvd/slides.pdf.

• E. Friedrich, "The Voronoi diagram in structural optimisation," UCL Discovery, https://discovery.ucl.ac.uk/document.pdf, 2008.

• H. Ledoux, "Computing the 3D Voronoi Diagram Robustly," GDMC, https://gdmc.nl/publications/Computing_3D_Voronoi.pdf, 2007.

• D. Lee, "On k-Nearest Neighbor Voronoi Diagrams in the Euclidean Plane," amedeolucente.it, https://amedeolucente.it/public/VORONOI.pdf, 1982.

• UPC Universitat Politècnica de Catalunya, "STORING THE VORONOI DIAGRAM," UPC, https://dccg.upc.edu/uploads/2020/06/GeoC.pdf.

• M. Mumm, "Voronoi Diagrams," ScholarWorks at University of Montana, https://scholarworks.umt.edu/viewcontent.pdf, 2004.

• M. Erwig, "The Graph Voronoi Diagram with Applications," Oregon State University, https://web.engr.oregonstate.edu/~erwig/papers.pdf.

• Johns Hopkins University, "Voronoi Diagrams and Delaunay Triangulations," Johns Hopkins University, https://www.cs.jhu.edu/~misha/Spring16.pdf.

• UCSB Computer Science, "Voronoi Diagrams," UCSB, https://sites.cs.ucsb.edu/~suri/Voronoi.pdf, 2019.

• Beijing University, "3. Voronoi Diagrams," Beijing University, https://www.math.pku.edu.cn/Note/vmsc.pdf.

• K. E. Hoff III, "Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware," CMU School of Computer Science, https://www.cs.cmu.edu/sbp_papers/integrated3.pdf, 2010.

• Bowdoin College, "Voronoi Diagram," Bowdoin College, https://tildesites.bowdoin.edu/Slides/cg-voronoi.pdf.

• University of Florida, "Lecture 7: Voronoi diagrams," University of Florida, https://www.cise.ufl.edu/kreveldmorevoronoi.pdf.

• Columbia University, "Voronoi Path Planning," Department of Computer Science, Columbia University, https://www.cs.columbia.edu/~allen/NOTES.pdf.

• Duke University, "Lecture 11: Voronoi diagram, Delaunay triangulation," Duke University, https://courses.cs.duke.edu/fall05/cps234/notes.pdf, 2005.

• F. Anton, "The Voronoi diagram of circles and its application to the Euclidean Plane," Danmarks Tekniske Universitet - DTU, http://www2.imm.dtu.dk/Anton_etal_2009.pdf.

• Cornell University, "Voronoi diagrams and applications," Cornell Computer Science Department, https://www.cs.cornell.edu/courses/lectures.pdf.

• Calculate, "Voronoi Diagrams Exercises," Calculate, https://calculate.org.au/uploads/sites/2019/01/Voronoi.pdf.

• D. Tubbenhauer, "What is...a Voronoi diagram? Or: Distance diagrammatically," Daniel Tubbenhauer, https://www.dtubbenhauer.com/slides/72-voronoi.pdf.

• Y. Li, "Area Queries Based on Voronoi Diagrams," arXiv, https://arxiv.org/pdf.pdf, 2019.

• E. T. K. Sang, "VORONOI DIAGRAMS WITHOUT BOUNDING BOXES," ResearchGate, https://www.researchgate.net/fulltext/VORONOI.pdf, 2015.

• K. Lu, "HVS: Hierarchical Graph Structure Based on Voronoi," VLDB Endowment, https://www.vldb.org/pvldb/vol15/p246-lu.pdf.

• University of California, Irvine, "Voronoi Diagrams," University of California, Irvine, https://ics.uci.edu/teach/geom/notes/Voronoi.pdf.

• TU Delft, "Tetrahedralisations and 3D Voronoi diagrams," TU Delft 3D Geoinformation, https://3d.bk.tudelft.nl/data/handout2.2.pdf, 2021.

• H. Imai, "Voronoi Diagram in the Laguerre Geometry and Its Applications," Simon Fraser University, https://www2.cs.sfu.ca/~binay/LaguerreGeometry.pdf, 1985.

• TI Education, "Voronoi Activity," TI Education, https://education.ti.com/media.pdf.

• Inria, "Voronoi Diagrams, Delaunay Triangulations and Polytopes," Inria, https://team.inria.fr/files/2016/01/2-delaunay-1.pdf.

• S. Fortune, "27 VORONOI DIAGRAMS AND DELAUNAY," University Northridge, http://www.csun.edu/~ctoth/Handbook/chap27.pdf.

• Universidad de Sevilla, "Lecture 11: Voronoi diagrams," Universidad de Sevilla, https://personal.us.es/almar/11voronoi.pdf.

• Drones and Autonomous Systems Lab, "Introduction to Voronoi Diagrams," DASL, https://www.daslhub.org/wiki/lib/exe/fetch.pdf.

• R. C. Lindenbergh, "Voronoi diagrams," Universiteit Utrecht, https://dspace.library.uu.nl/bitstream/handle.pdf, 2002.

• Rensselaer Polytechnic Institute (RPI), "Lecture 10: Voronoi Diagrams, Part 1," RPI, https://www.cs.rpi.edu/~cutler/classes/lectures.pdf.

• UMD Computer Science, "Lecture 11 Voronoi Diagrams and Fortune's Algorithm," UMD, https://www.cs.umd.edu/class/Lects/lect11-vor.pdf.

• K. Q. Brown, "Voronoi Diagrams from Convex Hull," Department of Mathematics, Washington University in St. Louis, https://www.math.wustl.edu/pmf/KQBrown.pdf, 1979.

• UBC Computer Science Department, "1 Voronoi Diagram," UBC, https://www.cs.ubc.ca/~will/scribe.pdf, 2022.