CoreSource checked

Voronoi Diagram

Partitions space into regions closest to each input site.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Geometry
Difficulty: Advanced
Family: Spatial Partitioning
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 9
Code example: Not ready
Visualization: Ready
Aliases: Voronoi Tessellation

Overview

A Voronoi Diagram divides a plane so every point in a cell is nearest to that cell's site.

Core Concepts

geometric calculationgeometric predicatespatial partitionspatial partitioningspatial relationshipcoordinate calculation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use Voronoi Diagram when you need to compute nearest-site regions.
Use it for spatial analysis with inputs like set of sites or points.
Use it when the problem depends on spatial relationships between points, lines, or shapes.
Use it when the Spatial Partitioning tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when floating-point precision or degenerate cases are not handled.
Avoid it when O(n^2) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not voronoi cells and edges.

What It Does

Computes nearest-site regions
Builds boundaries halfway between sites

Use Cases

Spatial analysis
Procedural regions
Nearest facility maps

Inputs

Set of sites or points

Outputs

Voronoi cells and edges

Key Formulas (1)

Voronoi region

region_i = points p where distance(p, site_i) ≤ distance(p, site_j) for every j

region_i = points p where distance(p, site_i) <= distance(p, site_j) for every j

Defines each cell as the points closest to one input site.

Pseudocode

1.Process sites with a sweep or triangulation method
2.Find boundaries equidistant from neighboring sites
3.Assemble cell edges
4.Clip cells to the domain if needed
5.Return the partition

Canonical Example

Input: points = [(0,0), (2,0), (1,1), (1,0)]
Output: spatial result such as a boundary, intersection, or containment answer
Explanation: Voronoi Diagram: The algorithm uses geometric tests to reason about the input shapes.

Implementation Notes

Keep the input contract explicit: Set of sites or points.
Use this step as the implementation spine: Process sites with a sweep or triangulation method.
Then preserve the next state change: Find boundaries equidistant from neighboring sites.
Write tests for points on boundaries, equal coordinates, and very small distances.

Common Pitfalls

Voronoi diagrams can be derived from Delaunay triangulations.
Forgetting collinear, duplicate, overlapping, or boundary cases.
Returning voronoi cells and edges without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Show points claiming surrounding regions of the plane.

Step 1 of 5: Process sites with a sweep or triangulation method

nearest-site-cells

Notes

Voronoi Diagram operates in O(n log n) time and O(n) space within the Spatial Partitioning family. Key governing relation: region_i = points p where distance(p, site_i) <= distance(p, site_j) for every j. Often compared with Delaunay Triangulation and Quickhull.