[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico] [Índice de assunto]

triangularizacao de poligonos em O(n)



Oi pessoal
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

falo


Paulo Eduardo A. Silveira   <peas@linux.ime.usp.br>
UIN: 5142673   www.paulo.com.br