PHD
  1. Algebra  1.1. Group Theory  1.1.1. Basic Properties of Groups  1.1.2. Subgroups  1.1.3. Cosets and Lagrange's Theorem  1.1.4. Normal Subgroups  1.1.5. Quotient Groups  1.1.6. Group Homomorphisms  1.1.7. Sylow Theorems  1.1.8. Free Groups  1.1.9. Group Actions  1.1.10. Simple and Solvable Groups  1.2. Ring Theory  1.2.1. Rings and Ideals  1.2.2. Ring Homomorphisms  1.2.3. Polynomial Rings  1.2.4. Principal Ideal Domains  1.2.5. Unique Factorization Domains  1.2.6. Noetherian Rings  1.2.7. Artinian Rings  1.3. Field Theory  1.3.1. Field Extensions  1.3.2. Splitting Fields  1.3.3. Galois Theory  1.3.4. Algebraic Closures  1.3.5. Finite Fields  1.3.6. Transcendental Extensions  1.4. Module Theory  1.4.1. Modules over Rings  1.4.2. Free Modules  1.4.3. Module Homomorphisms  1.4.4. Simple and Semi-Simple Modules  1.4.5. Projective Modules  1.4.6. Injective Modules  1.5. Linear Algebra  1.5.1. Vector Spaces  1.5.2. Linear Transformations  1.5.3. Eigenvalues and Eigenvectors  1.5.4. Canonical Forms  1.5.5. Inner Product Spaces  1.5.6. Spectral Theorem  1.5.7. Singular Value Decomposition
  2. Analysis  2.1. Real Analysis  2.1.1. Real Numbers and Completeness  2.1.2. Sequences and Series  2.1.3. Continuity  2.1.4. Differentiation  2.1.5. Riemann Integration  2.1.6. Metric Spaces  2.1.7. Lebesgue Measure  2.2. Complex Analysis  2.2.1. Complex Numbers  2.2.2. Analytic Functions  2.2.3. Contour Integration  2.2.4. Cauchy's Theorem  2.2.5. Residue Theorem  2.2.6. Conformal Mappings  2.3. Functional Analysis  2.3.1. Normed Spaces  2.3.2. Banach Spaces  2.3.3. Hilbert Spaces  2.3.4. Linear Operators  2.3.5. Spectral Theory  2.3.6. Compact Operators  2.4. Measure Theory  2.4.1. Sigma Algebras  2.4.2. Measures and Integrals  2.4.3. Lebesgue Integration  2.4.4. Convergence Theorems  2.4.5. Fubini's Theorem  2.5. Harmonic Analysis  2.5.1. Fourier Series  2.5.2. Fourier Transforms  2.5.3. Distribution Theory  2.5.4. Wavelets
  3. Topology  3.1. General Topology  3.1.1. Open and Closed Sets  3.1.2. Continuity  3.1.3. Compactness  3.1.4. Connectedness  3.1.5. Metric Topology  3.2. Algebraic Topology  3.2.1. Fundamental Groups  3.2.2. Homotopy Theory  3.2.3. Homology Theory  3.2.4. Cohomology  3.2.5. Exact Sequences  3.3. Differential Topology  3.3.1. Smooth Manifolds  3.3.2. Tangent Spaces  3.3.3. Vector Fields  3.3.4. Differential Forms
  4. Geometry  4.1. Differential Geometry  4.1.1. Curves and Surfaces  4.1.2. Riemannian Geometry  4.1.3. Geodesics  4.1.4. Curvature  4.2. Algebraic Geometry  4.2.1. Affine and Projective Varieties  4.2.2. Schemes  4.2.3. Divisors and Intersections  4.2.4. Cohomology in Algebraic Geometry  4.3. Computational Geometry  4.3.1. Convex Hulls  4.3.2. Triangulations  4.3.3. Voronoi Diagrams  4.3.4. Geometric Algorithms
  5. Number Theory  5.1. Elementary Number Theory  5.1.1. Divisibility  5.1.2. Congruences  5.1.3. Modular Arithmetic  5.2. Analytic Number Theory  5.2.1. Prime Number Theorem  5.2.2. Dirichlet Series  5.2.3. Zeta and L-functions  5.3. Algebraic Number Theory  5.3.1. Number Fields  5.3.2. Ideals  5.3.3. Class Groups  5.3.4. Galois Representations
  6. Combinatorics  6.1. Enumerative Combinatorics  6.1.1. Generating Functions  6.1.2. Recurrence Relations  6.1.3. Permutations and Combinations  6.2. Graph Theory  6.2.1. Graph Isomorphisms  6.2.2. Planarity  6.2.3. Graph Coloring  6.3. Extremal Combinatorics  6.3.1. Ramsey Theory  6.3.2. Probabilistic Methods in Extremal Combinatorics  6.4. Algebraic Combinatorics  6.4.1. Matrix Methods  6.4.2. Representation Theory
  7. Logic and Foundations  7.1. Set Theory  7.1.1. Zermelo-Fraenkel Axioms  7.1.2. Ordinals and Cardinals  7.2. Model Theory  7.2.1. Structures and Theories in Model Theory  7.2.2. Compactness Theorem  7.3. Proof Theory  7.3.1. Formal Systems  7.3.2. Consistency and Completeness
  8. Probability and Statistics  8.1. Probability Theory  8.1.1. Random Variables  8.1.2. Expectation and Variance  8.1.3. Central Limit Theorem  8.2. Stochastic Processes  8.2.1. Markov Chains  8.2.2. Brownian Motion  8.3. Statistical Inference  8.3.1. Hypothesis Testing  8.3.2. Regression Analysis
  9. Applied Mathematics  9.1. Numerical Analysis  9.1.1. Iterative Methods  9.1.2. Interpolation  9.1.3. Error Analysis  9.2. Partial Differential Equations  9.2.1. Elliptic Equations  9.2.2. Parabolic Equations  9.2.3. Hyperbolic Equations  9.3. Dynamical Systems  9.3.1. Chaos Theory  9.3.2. Stability Analysis in Dynamical Systems

PHD → Geometry → Computational Geometry ↓


Voronoi Diagrams


Voronoi diagrams are an essential part of computational geometry, providing a way to divide a plane into regions based on the distance from a set of specific points known as sites. The concept is named after Russian mathematician Georgi Voronoi. These diagrams have a wide range of applications, including computer graphics, geographic information systems (GIS), and even biology.

What is a Voronoi diagram?

Imagine a flat, infinite plane. Now place some points anywhere on this plane, which we will call sites. The Voronoi diagram of these sites divides the plane into regions where each site has a corresponding region consisting of all points closer to it than to any other site. These regions are known as Voronoi cells.

Mathematically, the Voronoi cell corresponding to a site P_i consists of all the points P as follows:

|P - P_i| < |P - P_j| for every j ≠ i

Here, |P - P_i| denotes the distance between point P and site P_i.

Visualization of Voronoi diagrams

To understand the Voronoi diagram better, let's consider some examples. Below is a simple Voronoi diagram with three sites:

In this diagram, each colored circle represents a site. The dashed lines indicate boundaries where the distance from a site to a point on the boundary is the same for the two sites. Each segment separated by the lines forms a Voronoi cell. For example, the upper-left region contains all the points that are closer to the red site than to any other site.

Bisectors and Voronoi edges

When creating a Voronoi diagram, an important concept is the bisector. A bisector is a set of points in the plane that are equidistant from the two nearest sites. Where the points of two sites are equidistant, the boundary is called a Voronoi edge.

For two sites P_i and P_j, the bisector can be described by the collection of all points P such that:

|P - P_i| = |P - P_j|

This line is the midpoint in terms of distance between the two sites, and any point crossing it will change its nearest site association between P_i and P_j.

Mathematical constructions

Constructing a Voronoi diagram involves mathematically constructing these boundaries for each pair of sites. For a given finite set of n sites {P_1, P_2, ..., P_n}, the Voronoi edge is calculated as follows:

|P - P_i| = |P - P_j|, for all i ≠ j

Each pair of sites gives rise to a one-dimensional space of points (lines) that serve as potential boundaries for Voronoi regions. The intersection of these lines forms the vertices where multiple cells meet.

Properties of Voronoi diagram

Voronoi diagrams have several attractive properties:

  • Uniqueness: For a finite set of sites, the Voronoi diagram is unique, provided it has normality and no collinearity.
  • Convexity: Each Voronoi cell is usually a convex polygon because the region closer to one site compared to other sites forms a convex shape.
  • Duality: The Delaunay triangulation is the dual graph of the Voronoi diagram. It consists of edges connecting pairs of sites with their Voronoi neighbors.
  • Coplanarity: The Voronoi diagram divides the plane in such a way that no boundaries overlap, and this ensures that each point belongs to only one location.

Applications of Voronoi diagrams

Voronoi diagrams have wide application in various fields:

  • Geographic Information Systems (GIS): Voronoi diagrams can be used to analyze spatial structures and divide geographic locations based on proximity. They can show how areas are divided based on economic influence, such as store locations.
  • Computer graphics: Voronoi diagrams are used in procedural texture generation, modeling, and rendering to create natural-looking images and surfaces.
  • Robotics: For path planning and determining the workspace of a robot with multiple obstacles.
  • Biology: Studying cell structures where cells grow relative to several main growth centers.

Construction of Voronoi diagrams using algorithms

Several algorithms exist for computing Voronoi diagrams, ranging from simple methods to more efficient algorithms:

  • Simple approach: This involves checking the nearest site of each point by calculating its distance from each site, which is computationally expensive.
  • Fortune's Algorithm: A powerful sweep line algorithm that constructs a Voronoi diagram in O(n log n) time. It uses the middle line to sweep across the plane and sequentially construct a solution.

Fortune's algorithm works by advancing a sweep line from top to bottom, maintaining a priority queue (event queue) of active arcs and a status structure (between line). It efficiently finds events such as circle events where arcs disappear.

Limitations and challenges

Despite their powerful applications, Voronoi diagrams can be complicated to deal with due to the following:

  • Higher dimensions: Extending Voronoi diagrams to 3D (or higher) geometry is complicated because dihedral angles and polyhedra take the place of lines and polygons.
  • Numerical stability: Calculating exact distances introduces precision errors, leading to inaccurate cell boundaries.
  • Large datasets: Computing Voronoi diagrams for large datasets can be computationally intensive, requiring optimized algorithms and careful memory management.

Voronoi diagrams beyond Euclidean space

While Voronoi diagrams are usually based on Euclidean distance, variations exist for different distance measures:

  • Manhattan distance: shapes the Voronoi diagram based on the sum of the horizontal and vertical distances, resulting in diamond-shaped cells.
  • Minkowski distance: a generalized form leading to different cell shapes depending on the chosen value of p in the distance formula. 
    d(P_i, P_j) = ( |x2 − x1|^p + |y2 − y1|^p )^(1/p)

Conclusion

Voronoi diagrams present an elegant way to approach spatial partitioning based on proximity. Whether applied in graphics, robotics, or biology, they play a key role in solving problems that involve partitioning space based on the nearest site. As computational methods advance, the calculation of Voronoi diagrams becomes more and more feasible for complex, high-dimensional problems, making them an indispensable tool in fields such as computational geometry and beyond.


PHD → 4.3.3


U
username
0%
completed in PHD

← Prev (4.3.2)
Triangulations
Next (4.3.4) →
Geometric Algorithms

Comments 



Voronoi Diagrams

https://www.buddymath.com/phd/4.3.3?bmal=en