📐Discrete Geometry Unit 5 – Voronoi Diagrams & Delaunay Triangulations

What's the Big Idea?

• Voronoi diagrams partition a plane into regions based on distance to specified points called sites
• Each region contains all points closer to its site than to any other site
• Delaunay triangulations connect sites that share a Voronoi edge, forming a dual graph
• Voronoi diagrams and Delaunay triangulations have wide-ranging applications in various fields
  • Used in computational geometry, computer graphics, geographic information systems (GIS), and more
• Efficient algorithms exist for constructing Voronoi diagrams and Delaunay triangulations
• Voronoi diagrams and Delaunay triangulations possess several interesting mathematical properties
  • Delaunay triangulation maximizes the minimum angle among all possible triangulations

Key Concepts and Definitions

• Sites: The specified points in the plane used to construct the Voronoi diagram
• Voronoi cell (or region): The set of points closer to a particular site than to any other site
• Voronoi edge: The boundary between two adjacent Voronoi cells
• Voronoi vertex: A point equidistant from three or more sites, formed by the intersection of Voronoi edges
• Delaunay triangulation: A triangulation of the sites where no site lies inside the circumcircle of any triangle
  • Connects sites that share a Voronoi edge
• Dual graph: A graph formed by connecting the sites of a Voronoi diagram, resulting in the Delaunay triangulation
• Convex hull: The smallest convex polygon that encloses all the sites
• Circumcircle: A circle that passes through all three vertices of a triangle

Historical Background

• Voronoi diagrams named after Georgy Voronoy, a Ukrainian mathematician who defined and studied them in 1908
• Voronoi-like structures appeared in earlier works by Descartes (1644) and Dirichlet (1850)
• Delaunay triangulations named after Boris Delaunay, a Russian mathematician who introduced them in 1934
• Voronoi diagrams and Delaunay triangulations gained popularity in computational geometry during the 1970s and 1980s
  • Advancements in computer technology and algorithm design fueled their growth
• Today, Voronoi diagrams and Delaunay triangulations are fundamental tools in various fields
  • Computer graphics, geographic information systems (GIS), robotics, and more

Constructing Voronoi Diagrams

• Naive approach: Compute the bisector between each pair of sites and intersect them to form Voronoi edges and vertices
  • Time complexity: $O(n^3)$ for $n$ sites
• Incremental construction: Add sites one by one, updating the Voronoi diagram with each addition
  • Time complexity: $O(n^2)$ for $n$ sites
• Divide-and-conquer: Recursively divide the set of sites into subsets, construct Voronoi diagrams for each subset, and merge them
  • Time complexity: $O(n \log n)$ for $n$ sites
• Fortune's algorithm: A sweep-line algorithm that maintains a beach line and a queue of site events
  • Time complexity: $O(n \log n)$ for $n$ sites
• Delaunay triangulation: Construct the Delaunay triangulation first, then derive the Voronoi diagram as its dual graph

Properties of Voronoi Diagrams

• Each Voronoi cell is a convex polygon
• Voronoi edges are straight line segments or half-lines
• Voronoi vertices have degree three or higher
• The number of Voronoi vertices, edges, and cells satisfies Euler's formula: $V - E + F = 2$
  • $V$: number of Voronoi vertices, $E$: number of Voronoi edges, $F$: number of Voronoi cells (including the unbounded cell)
• The nearest neighbor of a point is the site of the Voronoi cell containing that point
• The Voronoi diagram of a set of sites is unique

Delaunay Triangulations: The Dual Graph

• Delaunay triangulation connects sites that share a Voronoi edge
• Dual relationship: Voronoi vertices correspond to Delaunay triangles, and Voronoi edges correspond to Delaunay edges
• Empty circle property: No site lies inside the circumcircle of any Delaunay triangle
  • Ensures that the triangulation maximizes the minimum angle among all possible triangulations
• Uniqueness: The Delaunay triangulation is unique for a set of sites in general position (no four sites are cocircular)
• Convex hull: The outer edges of the Delaunay triangulation form the convex hull of the sites
• Flipping edges: Delaunay triangulation can be obtained by flipping edges in an arbitrary triangulation until the empty circle property is satisfied

Applications in Real Life

• Nearest neighbor search: Voronoi diagrams can efficiently find the nearest site to a given point
  • Used in facility location problems (e.g., placing hospitals or fire stations)
• Path planning: Voronoi diagrams can generate safe paths that maximize distance from obstacles
  • Applied in robotics and autonomous navigation
• Interpolation and sampling: Delaunay triangulations are used for interpolating scattered data points
  • Employed in terrain modeling, climate analysis, and computer graphics
• Mesh generation: Delaunay triangulations provide quality triangular meshes for finite element analysis
  • Used in engineering simulations and scientific computing
• Clustering and data analysis: Voronoi diagrams can help identify clusters and outliers in datasets
  • Applied in pattern recognition, machine learning, and data mining

Computational Methods and Algorithms

• Incremental insertion: Incrementally add sites and update the Voronoi diagram or Delaunay triangulation
  • Bowyer-Watson algorithm for Delaunay triangulation
• Divide-and-conquer: Recursively divide the problem into subproblems, solve them, and merge the results
  • Shamos-Hoey algorithm for Voronoi diagrams
• Sweep-line techniques: Maintain a sweeping line and process events as the line moves across the plane
  • Fortune's algorithm for Voronoi diagrams
• Randomized incremental construction: Add sites in random order and update the structure incrementally
  • Clarkson-Shor algorithm for Delaunay triangulation
• Flipping-based algorithms: Start with an arbitrary triangulation and flip edges until the Delaunay property is satisfied
  • Lawson's algorithm for Delaunay triangulation

Advanced Topics and Extensions

• Higher dimensions: Voronoi diagrams and Delaunay triangulations can be generalized to higher-dimensional spaces
  • Applications in data analysis, machine learning, and computational geometry
• Weighted Voronoi diagrams: Each site is assigned a weight, affecting the shape and size of its Voronoi cell
  • Used in facility location problems with varying importance of sites
• Power diagrams (or Laguerre Voronoi diagrams): A generalization of Voronoi diagrams using circles instead of points as sites
  • Applied in surface reconstruction and molecular modeling
• Farthest-point Voronoi diagrams: Partition the plane based on the farthest site instead of the nearest
  • Used in largest empty circle problems and collision detection
• Voronoi diagrams on spheres and other surfaces: Constructing Voronoi diagrams on non-Euclidean spaces
  • Applications in geospatial analysis and computer graphics