Diagram Woronoja

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Komórki Woronoja dla losowego zbioru punktów na płaszczyźnie.

W matematyce Diagram Woronoja (zwany też tesselacją Woronoja, lub komórkami Woronoja) to graf nazwany tak na cześć Gieorgija Woronoja.

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

[edytuj] Definicja

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

$Vor_S(p)=\{x\in E /\forall q\in S , d(x,p) \le d(x,q)\}$ , gdzie $d$ jest odleglością.

Weźmy dwa punkty $a$ i $b$ należące do zbioru $S$ . W przestrzeni dwuwymiarowej $E$ (płaszczyzna) zbiór $Π(a, b)$ punktów jednakowo odległych od $a$ i od $b$ jest prostą zwaną symetralną odcinka $a b$ : $\Pi(a,b)=\{x\in E / d(x,a) = d(x,b)\}$ .

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

Niech $H (a, b)$ będzie półpłaszczyzną ograniczoną prostą $Π(a, b)$ i zawierającą punkt $a$ . Zawiera więc ona wszystkie punkty bliższe punktowi $a$ niż punktowi $b$ : $H(a,b)=\{x\in E / d(x,a) \le d(x,b)\}$ .

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

$Vor_S(a)= \displaystyle\bigcap_{b\in S - \{a\}} H(a,b)$ .

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

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

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 $p$ i $q$ tworzą krawędź grafu wtedy i tylko wtedy gdy komórki Woronoja przyporządkowane tym punktom przystają do siebie:

$Del(S) = \{(p,q)\in S^2 / Vor_S(p) \cap Vor_S(q) \not= 0 \}$