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.

Voronoi-diagram van een willekeurige verzameling punten

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

bewerken

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

bewerken

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

bewerken

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

bewerken

Bronvermelding

bewerken