Diagram Woronoja

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Komórki Woronoja dla losowego zbioru punktów na płaszczyźnie.

Diagram Woronoja (zwany również tesselacją Dirichleta, tesselacją Woronoja lub komórkami Woronoja, ang. Voronoi diagram) – podział płaszczyzny, nazwany tak na cześć Gieorgija Woronoja (termin tesselacja Dirichleta pochodzi od nazwiska Petera Dirichleta).

W przypadku przestrzeni dwuwymiarowej, dla danego zbioru punktów, dzieli się płaszczyznę na obszarów, w taki sposób, że każdy punkt w dowolnym obszarze znajduje się bliżej określonego punktu ze zbioru punktów niż od pozostałych punktów

Definicja formalna[edytuj]

Niech będzie skończonym zbiorem punktów należących do przestrzeni euklidesowej . Elementy zbioru nazwiemy centrami, środkami lub zalążkami. Obszarem Woronoja lub komórką Woronoja przypisaną pewnemu elementowi zbioru nazwiemy zbiór punktów znajdujących się bliżej punktu niż każdego innego elementu ze zbioru :

, gdzie jest odległością.

Weźmy dwa punkty i należące do zbioru . W przestrzeni dwuwymiarowej (płaszczyzna) zbiór punktów jednakowo odległych od i od jest prostą zwaną symetralną odcinka : .

Prosta ta jest granicą między zbiorem punktów mniej oddalonych od punktu niż od punktu a zbiorem punktów mniej oddalonych od punktu niż od punktu .

Niech będzie półpłaszczyzną ograniczoną prostą i zawierającą punkt . Zawiera więc ona wszystkie punkty bliższe punktowi niż punktowi : .

Komórką (obszarem) Woronoja przypisaną punktowi jest intersekcja (część wspólna) wszystkich półpłaszczyzn , gdzie zastępuje kolejno każdy punkt ze zbioru .

.

Komórki Woronoja będąc intersekcją półpłaszczyzn są wielobokami wypukłymi. Zbiór tych wieloboków rozbija dwuwymiarową przestrzeń euklidesową i jest diagramem Woronoja odpowiadającym zbiorowi .

Omówiony podział płaszczyzny na komórki Woronoja można również zastosować w przestrzeni trójwymiarowej. Prosta zastąpiona będzie wówczas płaszczyzną , a półpłaszczyzna półprzestrzenią ograniczoną płaszczyzną . Przestrzenne komórki Woronoja są wielościanami wypukłymi. Generalizując, w przestrzeni euklidesowej -wymiarowej , jest hiperpłaszczyzną afiniczną (wymiaru ), a dowolna komórka Woronoja będąc intersekcją półprzestrzeni wymiaru N, ograniczonych hiperpłaszczyznami jest wielokomórką wypukłą.

Diagram Woronoja (na czerwono) i triangulacja Delone.

Diagram Woronoja jest grafem dualnym triangulacji Delone, którą można zresztą łatwo otrzymać na podstawie diagramu Woronoja: dwa punkty i tworzą krawędź grafu wtedy i tylko wtedy gdy komórki Woronoja przyporządkowane tym punktom przystają do siebie: