Diagram Woronoja

Diagram Woronoja, tesselacja Dirichleta, tesselacja Woronoja lub komórki Woronoja (ang. Voronoi diagram) – podział płaszczyzny, nazwany tak na cześć twórcy Gieorgija Woronoja (termin tesselacja Dirichleta pochodzi od nazwiska Petera Dirichleta).

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

Definicja formalna

Niech ${\displaystyle S}$ będzie skończonym zbiorem ${\displaystyle n}$ punktów należących do przestrzeni euklidesowej ${\displaystyle E.}$ Elementy zbioru ${\displaystyle S}$ nazwiemy centrami, środkami lub zalążkami.

Obszarem Woronoja lub komórką Woronoja przypisaną pewnemu elementowi ${\displaystyle p}$ zbioru ${\displaystyle S}$ nazwiemy zbiór punktów znajdujących się bliżej punktu ${\displaystyle p}$ niż każdego innego elementu ze zbioru ${\displaystyle S{:}}$

${\displaystyle Vor_{S}(p)=\{x\in E|\forall q\in S,d(x,p)\leq d(x,q)\},}$

gdzie ${\displaystyle d}$ jest odległością.

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

${\displaystyle \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 ${\displaystyle a}$ niż od punktu ${\displaystyle b}$ a zbiorem punktów mniej oddalonych od punktu ${\displaystyle b}$ niż od punktu ${\displaystyle a.}$

Niech ${\displaystyle H(a,b)}$ będzie półpłaszczyzną ograniczoną prostą ${\displaystyle \Pi (a,b)}$ i zawierającą punkt ${\displaystyle a.}$ Zawiera więc ona wszystkie punkty bliższe punktowi ${\displaystyle a}$ niż punktowi ${\displaystyle b{:}}$

${\displaystyle H(a,b)=\{x\in E|d(x,a)\leq d(x,b)\}.}$

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

${\displaystyle Vor_{S}(a)=\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ą ${\displaystyle E}$ i jest diagramem Woronoja odpowiadającym zbiorowi ${\displaystyle S.}$

Omówiony podział płaszczyzny na komórki Woronoja można również zastosować w przestrzeni trójwymiarowej. Prosta ${\displaystyle \Pi (a,b)}$ zastąpiona będzie wówczas płaszczyzną ${\displaystyle \Pi (a,b),}$ a półpłaszczyzna ${\displaystyle H(a,b)}$ półprzestrzenią ${\displaystyle H(a,b)}$ ograniczoną płaszczyzną ${\displaystyle \Pi (a,b).}$ Przestrzenne komórki Woronoja są wielościanami wypukłymi.

Generalizując, w przestrzeni euklidesowej ${\displaystyle N}$-wymiarowej, ${\displaystyle \Pi (a,b)}$ jest hiperpłaszczyzną afiniczną (wymiaru ${\displaystyle N-1}$), a dowolna komórka Woronoja będąc intersekcją półprzestrzeni ${\displaystyle H(a,b)}$ wymiaru N, ograniczonych hiperpłaszczyznami ${\displaystyle \Pi (a,b)}$ jest wielokomórką wypukłą.

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

${\displaystyle Del(S)=\{(p,q)\in S^{2}|Vor_{S}(p)\cap Vor_{S}(q)\not =0\}.}$

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Voronoi Diagram, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).