Dado um conjunto de
pontos S, existe mais de uma triangulação de seu fecho
convexo.
Qual de elas tem maior ângulo mínimo?
A resposta é a triangulação de Delaunay.
Criada pelo matemático russo
Boris Dealunay.
Na triangulação de Delaunay para toda aresta podemos
achar um círculo que contem os
vértices da aresta mas não contem outro ponto. Nós
fizemos um análise matemático sem
falar do diagrama de Voronoi, baseados nos livros
"Computational
Geometry: Algorithms
and Applications" e
"Geometry and Topology for Mesh Generation" e
implementamos
o algoritmo aleatorio incremental, que cria a
triangulação de Dealaunay adicionando a
cada passo um ponto de S, e construindo assim
triangulações sucessivas até acabar com
todos os pontos de S, e obtendo no final a
triangulação de Delaunay.
