RE: triangularizacao de poligonos em O(n)

[Jose Coelho de Pina <coelho@ime.usp.br>]

Salve,

Paulo Eduardo Azevedo Silveira writes:
 > como o professor disse na aula, os malucos invetaram um jeito de
 > traingularizar um poligono QUALQUER (nao monotono) em ordem
 > linear. Eu achei interessante e entao resolvi dar uma procurada.
 > vi muito rapido, mas ele usa uma linha de varredura. nao sei qual o pre
 > processamento que ele usa.
 > 
 > quem invetou o algoritmo foi esse cara (1991):
 > http://www.cs.princeton.edu/~chazelle/
 > 
 > mas tem um Edgar Ramos (brasileiro ?) que fez um algoritmo baseado no do
 > chazelle porem mais simples. o ps pode ser pego nesse pagina (tem 12
 > folhas soh e muita coisa eh soh para provar o lower bound)
 > 
 > http://www.cse.iitd.ernet.in/~rohitk/cg_homepage/abs/ramos.html
 > 

Bacana!

Seria legal ver esse algoritmo implementado. Alguém se candidata?  O algoritmo
é probabilístico --- gasta tempo esperado linear.  Algoritmos probabilísticos
são, geralmente, mais simples de implementar (o problema é fazer a análise...) e
usam algum gerador de números aleatórios.

O algoritmo do Chazelle é determinístico e é bem mais complicado.

té +,
coelho