Gdybyśmy mogli unieść się w górę, zobaczylibyśmy interesujące nas obiekty znajdujące się w okolicy. Jak szybko określić, który z nich jest najbliżej? W tym celu moglibyśmy wykorzystać diagram Woronoja.

Rys. 1 Diagram Woronoja

Załóżmy, że obiektom, którymi jesteśmy zainteresowani, odpowiada zbiór  punktów na płaszczyźnie, które będziemy nazywać centrami. Odległość między punktami  definiujemy jako

Zauważmy, że centrum zawsze należy do odpowiadającego mu obszaru. Co więcej, do każdego obszaru należy tylko jedno centrum. Granicę między obszarami dla dwóch centrów  i   wyznacza symetralna odcinka  Zatem obszar Woronoja dla  jest częścią wspólną półpłaszczyzn wyznaczanych przez symetralne odcinków (dla ) i zawierających  Stąd wniosek, że obszary Woronoja są wielokątami wypukłymi (ograniczonymi lub nie), a krawędzie diagramu Woronoja są odcinkami lub półprostymi. Liczba krawędzi diagramu Woronoja jest liniowa względem liczby centrów, co uzasadnimy nieco dalej.

Wierzchołki diagramu Woronoja znajdują się w tej samej odległości od co najmniej trzech najbliższych centrów. Aby uprościć dalsze rozważania, przyjmijmy, że wierzchołek diagramu jest częścią wspólną dokładnie trzech obszarów Woronoja. Wtedy centra obszarów mających wspólny wierzchołek wyznaczają trójkąt. Ponieważ przeciwległe wierzchołki czworokąta nie mogą wyznaczać dwóch par sąsiadujących obszarów Woronoja, więc dwie różne krawędzie takich trójkątów nie mają innych punktów wspólnych niż końce. Wszystkie zdefiniowane w ten sposób trójkąty tworzą tzw. triangulację Delaunay.

Zauważmy, że odpowiadające sobie krawędzie nie muszą się przecinać.

Triangulacja Delaunay jest grafem planarnym, a krawędzie ściany zewnętrznej wyznaczają otoczkę wypukłą zbioru  tzn. brzeg najmniejszego zbioru wypukłego zawierającego  Innymi słowy, wierzchołkami tej otoczki wypukłej są centra nieograniczonych obszarów Woronoja zbioru  Z własności grafów planarnych (twierdzenie Eulera) otrzymujemy, że liczba krawędzi triangulacji Delaunay jest liniowa względem liczby centrów. To pokazuje zarazem, że liczba krawędzi diagramu Woronoja jest liniowa względem liczby centrów.

Wierzchołki trójkąta należącego do triangulacji Delaunay wyznaczają okrąg o środku w wierzchołku diagramu Woronoja (gdyby na okręgu znajdowało się więcej centrów z   to wyznaczany przez nie wielokąt moglibyśmy striangulować na różne sposoby). Spróbujmy uogólnić ten fakt.

Rys. 2 Triangulacja Delaunay i euklidesowe minimalne drzewo rozpinające

Pokażmy jeszcze jedną ciekawą własność triangulacji Delaunay.

W obliczeniach numerycznych ma zastosowanie jeszcze jedna, znacznie trudniejsza do udowodnienia, własność triangulacji Delaunay. Uporządkujmy niemalejąco kąty wszystkich trójkątów tworzących dowolną triangulację  zbioru  Następnie uporządkujmy leksykograficznie wszystkie triangulacje zbioru tzn. dla  oraz  zachodzi

oraz

Wtedy triangulacja Delaunay będzie ostatnim elementem tego porządku, tzn. triangulacja ta maksymalizuje minimalny kąt w tworzących ją trójkątach.

Wiedząc, że diagram Woronoja i triangulacja Delaunay mają tyle interesujących własności, spróbujmy skonstruować te grafy. Oczywiście, na mocy ich dualności wystarczy znaleźć tylko jeden z nich. Aby wyznaczyć diagram Woronoja, można zastosować pewne standardowe metody, np. „dziel i zwyciężaj” lub zamiatanie.

Rys. 3 Rzut trójkąta triangulacji Delaunay na paraboloidę

Ale my znów spróbujemy unieść się w górę. Mianowicie, załóżmy, że punkty ze zbioru  należą do płaszczyzny  Zrzutujmy zbiór  równolegle do osi  na paraboloidę obrotową  Zauważmy, że obrazy punktów należących do okręgu zawartego w płaszczyźnie  będą współpłaszczyznowe. Rzeczywiście, jeśli punkt  spełnia równanie  to w przestrzeni trójwymiarowej punkt  należy do płaszczyzny  Zatem rzuty okręgów opisanych na trójkątach triangulacji Delaunay wyznaczają płaszczyzny przecinające paraboloidę i zawierające rzuty wierzchołków odpowiednich trójkątów. Co więcej, na mocy wypukłości paraboloidy obrotowej płaszczyzny te nie rozdzielają obrazów punktów z   gdyż wnętrza okręgów opisanych na trójkątach triangulacji Delaunay (których rzuty są odcinane z paraboloidy przez omawiane płaszczyzny) nie zawierają punktów z   Zatem rzuty ścian triangulacji Delaunay są ścianami otoczki wypukłej obrazów punktów z   a rzuty krawędzi triangulacji są krawędziami otoczki wypukłej.

Zatem nie pozostaje nam nic innego, jak znaleźć otoczkę wypukłą zbioru punktów w przestrzeni trójwymiarowej. Możemy to zrobić, stosując np. metodę „dziel i zwyciężaj”. Złożoność obliczeniowa tego algorytmu wynosi  Następnie rzutujemy z powrotem na płaszczyznę  ściany otoczki wypukłej ograniczające ją od dołu i w ten sposób otrzymujemy triangulację Delaunay zbioru  Ponieważ wszystkie rzutowania możemy wykonać w czasie  więc całkowita złożoność tego algorytmu wynosi  Jest on więc nie tylko prosty, ale też efektywny.

Można również wykazać, że rzut prostopadły na płaszczyznę  minimalnego wielościanu wypukłego  zawierającego paraboloidę  którego ściany zawierają się w płaszczyznach stycznych do tej paraboloidy w obrazach punktów z   jest diagramem Woronoja zbioru  Dowód tego faktu pozostawiamy Czytelnikowi jako ćwiczenie.