Triangulação
de Delaunay
9.4 Análise do Algorítmo
Veremos aqui a análise para o algorítmo randomico incremental visto anteriormente para computar a Triangulação de Delaunay de um conjunto de planos no plano.
Para a análise que se segue introduziremos aqui algumas notações:
Pr:={p1, p2, ..., pr} : conjunto de pontos inseridos até o r-ésimo passo do algorítmo;
DGr:=DG(Ω U Pr) : Diagrama de Delaunay para o conjunto de pontos Ω U Pr.
Tr : conjunto de triângulos de DGr.
K(Δ) : conjunto de pontos que estão contidos no circuncírculo de um dado triângulo Δ.
Teorema 9.12 - A Triangulação de Delaunay de um conjunto P de n pontos no plano pode ser computada em tempo esperada da ordem de O(n log n), usando um armazenamento de dados de ordem esperada O(n).
Para a demonstração do algorítmo faremos uso de dois lemas, Lema 9.11 e Lema 9.13.
Lema 9.11 - O número esperado de triângulos criados pelo algotírmo DelaunayTriangulation é no máximo 9n+1.
Lema 9.13 - Se P é um conjunto de pontos em posição geral, então
onde o somatório é sobre todos os triangulos de Delaunay Δ criados pelo algorítmo.