September 30, 2003 Lecture 8: Voronoi DiagramsVoronoi Diagrams(Slides mostly by Allen Miu)September 30, 2003 Lecture 8: Voronoi DiagramsPost Office: What is the area of service?qq : free pointee : Voronoi edgevv : Voronoi vertexpipi: site pointsSeptember 30, 2003 Lecture 8: Voronoi DiagramsDefinition of Voronoi Diagram• Let P be a set of n distinct points (sites) in the plane.• The Voronoi diagram of P is the subdivision of the plane into n cells, one for each site.• A point q lies in the cell corresponding to a site pi∈ P iff ||q-pi || < ||q-pj||, for each pi∈ P, j ≠ i.September 30, 2003 Lecture 8: Voronoi DiagramsDemohttp://www.diku.dk/students/duff/Fortune/http://wwwpi6.fernuni-hagen.de/GeomLab/VoroGlide/September 30, 2003 Lecture 8: Voronoi DiagramsJeff’s Erickson Web PageSee also the implementation page from Christopher Gold's site www.Voronoi.com. Enough already!! Delaunay triangulations and farthest point Delaunay triangulations using 3d convex hulls by Daniel Mark Abrahams-Gessel, fortunately stolen by Anirudh Modibefore the original page was taken off the Web. This is the best one!Convex hulls, Delaunay triangulations, Voronoi diagrams, and proximity graphs by James E. Baker, Isabel F. Cruz, Luis D. Lejter, Giuseppe Liotta, and Roberto Tamassia. Source code is available. Incremental Delaunay triangulations and Voronoi diagrams by Frank BossenVoronoi Diagram/Delaunay Triangulation by Paul Chew uses a randomized incremental algorithm with "brute force" point location. 2-Site Voronoi diagrams by Matt Dickerson, from the Middlebury College Undergraduate Research Project in Computational GeometryThe convex hull/Voronoi diagram applet from the GeomNet project provides a secure Java wrapper for existing (non-Java) code. The applet calls qhull to build its convex hulls and Steve Fortune's sweep2 to build its Voronoi diagrams. A forms interface to the same programs is also available. VoroGlide, by Christian Icking, Rolf Klein, Peter Köllner, and Lihong Ma. Smoothly maintains the convex hull, Voronoi diagram, and Delaunay triangulation as points are moved, illustrates incremental construction of the Delaunay triangulation, and includes a recorded demo. Now on a faster server! Delaunay triangulations by Geoff Leach compares several (very) naïve algorithms. Source code is available. Bisectors and Voronoi diagrams under convex (polygonal) distance functions by Lihong Ma. The diagram is updated on the fly while sites or vertices of the unit ball are inserted, deleted, or dragged around. Very cool! Delaunay triangulations and Dirichlet tesselations and a short applet-enhanced tutorial by Eric C. Olson The Voronoi Game by Dennis Shasha. Try to place points to maximize the area of your Voronoi regions. Higher-order Voronoi diagrams by Barry SchaudtTessy, yet another interactive Voronoi/Delaunay demo from Keith Voegele. Java not required. ModeMap, by David Watson, draws Voronoi diagrams, Delaunay triangulations, natural neighbor circles (circumcircles of Delaunay triangles), and (for the very patient) radial density contours on the sphere. Don't give it more than 80 points. Delaunay Triangulation from Zhiyuan Zhao's JAVA Gallery of Geometric AlgorithmsDelaunay Triangulation Demo at ESSI, Université de Nice/Sophia-Antipolis, France. X terminal required instead of Java. Extremely slow, at least on this side of the Atlantic.September 30, 2003 Lecture 8: Voronoi DiagramsVoronoi Diagram Example:1 siteSeptember 30, 2003 Lecture 8: Voronoi DiagramsTwo sites form a perpendicular bisectorVoronoi Diagram is a linethat extends infinitely in both directions, and thetwo half planes on eitherside.September 30, 2003 Lecture 8: Voronoi DiagramsCollinear sites form a series of parallel linesSeptember 30, 2003 Lecture 8: Voronoi DiagramsNon-collinear sites form Voronoi half lines that meet at a vertexA Voronoi vertex is the center of an emptycircle touching 3 or more sites.vHalf linesA vertex hasdegree ≥ 3September 30, 2003 Lecture 8: Voronoi DiagramsVoronoi Cells and SegmentsvSeptember 30, 2003 Lecture 8: Voronoi DiagramsVoronoi Cells and SegmentsvUnbounded CellBounded CellSegmentSeptember 30, 2003 Lecture 8: Voronoi DiagramsPop quizvWhich of the following is true for2-D Voronoi diagrams? Four or more non-collinear sites are…1. sufficient to create a bounded cell2. necessary to create a bounded cell3. 1 and 24. none of aboveSeptember 30, 2003 Lecture 8: Voronoi DiagramsPop quizvWhich of the following is true for2-D Voronoi diagrams? Four or more non-collinear sites are…1. sufficient to create a bounded cell2. necessary to create a bounded cell3. 1 and 24. none of aboveSeptember 30, 2003 Lecture 8: Voronoi DiagramsDegenerate Case: no bounded cells!vSeptember 30, 2003 Lecture 8: Voronoi DiagramsSummary of Voronoi PropertiesA point q lies on a Voronoi edge between sites piand pjiff the largest empty circle centered at q touches only piand pj– A Voronoi edge is a subset of locus of points equidistant from piand pjee : Voronoi edgevv : Voronoi vertexpipi: site pointsSeptember 30, 2003 Lecture 8: Voronoi DiagramsSummary of Voronoi PropertiesA point q is a vertex iff the largest empty circle centered at q touches at least 3 sites– A Voronoi vertex is an intersection of 3 more segments, each equidistant from a pair of sitesee : Voronoi edgevv : Voronoi vertexpipi: site pointsSeptember 30, 2003 Lecture 8: Voronoi DiagramsOutline• Definitions and Examples• Properties of Voronoi diagrams• Complexity of Voronoi diagrams• Constructing Voronoi diagrams– Intuitions– Data Structures– Algorithm• Running Time Analysis• Demo• Duality and degenerate casesSeptember 30, 2003 Lecture 8: Voronoi DiagramsVoronoi diagrams have linear complexity {v, e = O(n)}Intuition: Not all bisectors are Voronoi edges!ee : Voronoi edgepipi: site pointsSeptember 30, 2003 Lecture 8: Voronoi DiagramsVoronoi diagrams have linear complexity {v, e = O(n)}Claim: For n ≥ 3, v ≤ 2n − 5 and e ≤ 3n − 6Proof: (General Case)• Euler’s Formula: for connected, planar graphs,v – e + f = 2 Where:v is the number of verticese is the number of edgesf is the number of facesSeptember 30, 2003 Lecture 8: Voronoi DiagramsVoronoi diagrams have linear complexity {v, e = O(n)}Claim: For n ≥ 3, v ≤ 2n − 5 and e ≤ 3n − 6Proof: (General Case)• For Voronoi graphs, f = n  (v +1) – e + n = 2epip∞To apply Euler’s Formula, we“planarize” the Voronoi diagram by connecting half lines to an