Voronoi-diagram
Een Voronoi-diagram, Voronoi-betegeling, Voronoi-decompositie of Dirichlet-betegeling is in de wiskunde een opdeling in veelhoeken van een metrische ruimte. Die opdeling wordt door de afstand bepaald tot een verzameling van gekozen geïsoleerde punten in die ruimte. Het Voronoi-diagram is naar Georgy Voronoi genoemd en Johann Dirichlet was een Duitse wiskundige. Een betegeling van een vlak is een manier om dat vlak met veelhoeken te bedekken zonder dat zij elkaar overlappen. Het gaat in een Voronoi-diagram altijd om convexe veelhoeken.

Men gaat uit van een gegeven verzameling punten  in een vlak. Ieder punt  in  heeft een Voronoi-cel  om zich heen, die uit alle punten bestaat die dichter bij  liggen dan bij enige ander punt van dat vlak. Deze cellen zijn veelhoeken. De zijden van die veelhoeken zijn dan de punten in het vlak die even ver liggen van de twee dichtstbijzijnde punten, de hoekpunten zijn de punten die even ver weg liggen ten opzichte van drie of meer punten.

In de driedimensionele ruimte zijn de Voronoi-cellen veelvlakken, in het algemene geval zijn het polytopen.

Voronoi-diagrammen worden gebruikt in vele uiteenlopende gebieden, van informatica tot biologie of het vinden van het dichtstbijzijnde benzinestation, ziekenhuis of apotheek.

Definitie 
Laat  een verzameling punten in de euclidische ruimte zijn, waarvan alle ophopingspunten in  liggen. Voor bijna elk punt  in de euclidische ruimte, is er een punt van , die het dichtst bij  ligt. Bijna wordt toegevoegd om uitzonderingen aan te geven, waarbij een punt even dichtbij twee of meer punten van  ligt.

De voronoi-cel  van het -de punt in de verzameling wordt gedefinieerd als:

 

waarin  de afstand is tussen twee punten  en  in de euclidische ruimte . Voronoi-cellen worden ook Thiessen-veelhoeken genoemd.

Verband met Delaunay-triangulatie 
Voor het Voronoi-diagram van een verzameling bestaat een Delaunay-triangulatie van diezelfde verzameling, die de duale graaf van het diagram is. De hoekpunten van de Voronoi-cellen zijn de middelpunten van de omgeschreven cirkels in de Delaunay-triangulatie. Twee punten zijn in een Delaunay-triangulatie verbonden dan en slechts dan als hun Voronoi-cellen een gemeenschappelijk punt, een gemeenschappelijke Voronoi-zijde hebben.

Men kan in de praktijk Voronoi-diagrammen het eenvoudigst berekenen door eerst de Delaunay-triangulatie te vormen en daaruit het Voronoi-diagram af te leiden.

Variaties 
Er zijn verschillende soorten Voronoi-diagrammen. Als er voor de afstand  niet de euclidische afstand wordt genomen, maar een andere metriek, bijvoorbeeld de Manhattan-metriek, ontstaat er een ander soort Voronoi-diagram.

Voronoi-diagrammen kunnen worden geconstrueerd voor verzamelingen van punten op een bolvormig oppervlak.

Er kunnen in plaats van punten ook andere objecten worden genomen, zoals lijnstukken, segmenten van curves, cirkels of bollen in drie dimensies. Rond deze objecten kan vervolgens een Voronoi-diagram worden opgebouwd.

Websites 
 Triangle A two-dimensional quality mesh generator and Delaunay triangulator. software voor het maken van Delaunay-triangulaties en Voronoi-diagrammen

Bronvermelding
 

Diagram
Discrete wiskunde
Meetkunde