Voronoi-diagram

Voronoi-diagram van een willekeurige verzameling punten

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 $S$ in een vlak. Ieder punt $z$ in $S$ heeft een Voronoi-cel $V(z)$ om zich heen, die uit alle punten bestaat die dichter bij $z$ 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 $S$ een verzameling punten in de euclidische ruimte zijn, waarvan alle ophopingspunten in $S$ liggen. Voor bijna elk punt $x$ in de euclidische ruimte, is er een punt van $S$, die het dichtst bij $x$ ligt. Bijna wordt toegevoegd om uitzonderingen aan te geven, waarbij een punt even dichtbij twee of meer punten van $S$ ligt.

De voronoi-cel $R_{k}$ van het $k$-de punt in de verzameling wordt gedefinieerd als:

$R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\quad {\text{voor elke }}j\neq k\}$

waarin $d(a,b)$ de afstand is tussen twee punten $a$ en $b$ in de euclidische ruimte $X$. 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 $d(a,b)$ 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

• Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Voronoi diagram op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.