Voronoi-diagram

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Het Voronoi-diagram van een willekeurige verzameling punten in het vlak (alle punten liggen binnen de afbeelding).

In de wiskunde is een Voronoi-diagram een speciaal type decompositie van een metrische ruimte, die wordt bepaald door afstanden tot een specifiek geïsoleerd punt van objecten in de ruimte, dat wil zeggen door een discrete verzameling punten. Het Voronoi-diagram is vernoemd naar Georgy Voronoi en wordt ook wel een Voronoi-betegeling, een Voronoi-decompositie, Thiessenpolygonen of ook wel een Dirichlet-betegeling (naar de Duitse wiskundige Dirichlet) genoemd.

In het eenvoudigste geval gaat men uit van een gegeven verzameling punten S in het vlak, de Voronoi-zijden. Elke zijde (punt) z in S heeft een Voronoi-cel, ook wel een Dirichlet-cel, V(z), genoemd, die uit alle punten bestaat die dichter bij z liggen dan bij enige andere zijde. Deze cellen zijn veelhoeken; de randen van die veelhoeken zijn dan de punten in het vlak die even ver liggen van de twee dichtstbijzijnde zijden, de hoekpunten zijn de punten die even ver weg liggen ten opzichte van drie (of meer) zijden.

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 computerwetenschap tot biologie of het vinden van het dichtstbijzijnde benzinestation of ziekenhuis.

Definitie[bewerken]

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. Het woord "bijna" wordt gebruikt om uitzonderingen aan te geven, waar een punt x even dichtbij twee of meer punten van S ligt.

De Voronoi-cel R_k van het ke punt in de verzameling wordt gedefinieerd als:

 R_k = \{x \in X\,\, | \,\,d(x,P_k) \leq d(x, P_j)\,\, \text{voor elke}\,\, j\neq k\}.

waarin d(a,b) de afstand is tussen twee punten a en b in de Euclidische ruimte X.

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 als en slechts als hun Voronoi-cellen een gemeenschappelijke zijde hebben.

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

Variaties[bewerken]

Er zijn talrijke types van Voronoi-diagrammen. Als men voor de afstand d(a,b) niet de Euclidische afstand neemt maar een andere metriek, bijvoorbeeld de Manhattan-metriek, verkrijgt men een ander type Voronoi-diagram.

Men kan Voronoi-diagrammen construeren voor verzamelingen van punten op een bolvormig oppervlak.

Men kan in plaats van discrete punten ook andere verzamelingen nemen, bijvoorbeeld lijnstukken, segmenten van curves, cirkels, of bollen (in 3 dimensies) waarrond men dan een Voronoi-diagram opbouwt.

Externe links[bewerken]