Voroného diagram

V matematice Voroného (Thiessenův) diagram, nazvaný podle Georgije Voroného, někdy nazývaná Voroného teselace, Voroného dekompozice nebo Dirichletova teselace (podle Lejeune Dirichleta), je způsob dekompozice metrického prostoru určený vzdálenostmi k dané diskrétní množině objektů v prostoru, například diskrétní množinou bodů.

Nejjednodušším a nejběžnějším případem je rozdělení roviny podle dané množiny bodů M. Voroného diagram pro S je rozdělení roviny, která každému bodu b z M přidělí oblast V(b) tak, aby všechny body oblasti V(b) byly blíže k bodu b než k jakémukoliv jinému bodu z množiny M. Pro nalezení takového rozdělení se používá Fortunův algoritmus.

Jinou možností je aplikace přírůstkového (inkrementálního) algoritmu. Není tak efektivní jako jiné algoritmy, ale jeho princip je jednoduchý a intuitivní. Najdeme diagram pro nějaký jednoduchý případ (například vybereme dva nebo tři body z množiny generátoru) a pak postupně přidáváme po jednom zbylé body.

Voroného diagramy mají řadu využití v různých oborech, např. v geometrii, sociologii, chemii, hydrologii a dalších přírodních vědách, v urbanismu, architektuře. Mimo jiné se používají pro optimální rozdělení parcel, generování buněčných nebo krystalových struktur, pro voštinové struktury 3D tisku, v umění, ale třeba i ve fotbalu.

V meteorologii a hydrologii se Voroného diagramy používají pod názvem Thiessenovy polygony (pojmenováno po americkém meteorologovi Alfredu Thiessenovi). Slouží k vyhodnocení prostorových dat, zejména pro určení výšky srážky na dané území.

Externí odkazy

Obrázky, zvuky či videa k tématu Voroného diagram na Wikimedia Commons
Animace ruční tvorby Voroného diagramu
Interaktivní kreslení diagramu (flash)
Generování Voroného diagramu v AutoCADu