Computando Triangulação Delaunay usando Fecho Convexo

Há uma conexão entre o fecho convexo e a triangulação Delaunay, que foi descoberta em 1979 por Kevin Brown e completamente desenvolvida por Herbert Edelsbrunner e Raimund Seidel no início dos anos 80. O centro desta conexão envolve o paraboloide

 Seja S um conjunto de pontos no plano xy, sem 4 pontos co-circulares. Associado a cada site (x,y) um valor de "altura de terreno" de x2 + y2 . Este local estará exatamente dentro de um paraboloide. Agora encontre o fecho convexo deste conjunto de pontos em R3. Descarte as "faces de cima" deste fecho, aquelas faces que são visíveis olhando diretamente para baixo do eixo z do alto. Estas faces são chamadas de fecho convexo superior, enquanto as faces restantes são chamadas de fecho convexo inferior. O impressionante resultado da conexão entre o fecho convexo e a triangulação Delaunay é dado pelo seguinte teorema:

Dado um conjunto de pontos S em um plano xy, a triangulação Delaunay Del(S) é exatamente a projeção para o eixo xy do fecho convexo inferior dos pontos (x,  y, x2+y2).

A figura a seguir mostra 10 pontos no plano cuja triangulação resulta da projeção do fecho convexo inferior destes pontos localizados no paraboloide. A marca do círculo no plano mostra a origem em R2, o ponto no qual o paraboloide toca o plano.

Do cálculo multivariado, a equação da tangente plana ao ponto (a,b) é dada por:

Se este plano for deslocado para cima (na direção de z) pela distância de r2, obtemos um novo plano p dado por

Da geometria cônica, este plano p intercepta a paraboloide ao longo de uma elipse. A projeção dessa elipse sobre o plano xy obtida resolvendo as equações (4.1) e (4.3) produz

Prova: Escolha uma face t do fecho convexo inferior, e deixe π ser o plano definido pelos três pontos de T no parabolóide. Nós podemos mudar esse plano para baixo (na direção z) até que seja tangente à

parabolóide. Sejam (a, b​​, a2 + b2) o ponto de tangência e deixe r2 ser a quantidade de deslocamento para baixo em π. A equação do plano π é então dada por (4.3). 

Pela discussão anterior, a projeção no plano xy dos três pontos que definem t encontra-se em um círculo de raio r dada pela equação (4.4). Desde que t é uma face inferior do fecho convexo, todos os outros sites na paraboloide encontram acima de π, o que implica que se projetam para fora deste círculo de raio r. Portanto, este círculo determinado por t está vazio. pelo Teorema 3.53, a projeção de t para o plano xy é um triângulo Delaunay. Uma vez que isto é verdade para todos as faces do fecho convexo inferior, a projeção plena produz a triangulação de Delaunay.