Quick Hull
3179 palavras
13 páginas
Universidade Federal de S˜o Jo˜o del-Rei a aTrabalho Pratico 4
Convex Hull
Alan Lima Teles
Matheus Felipe Marques da Silva
6 de novembro de 2012
Sum´rio a 1 Introdu¸˜o ca 2 Problema proposto
2.1 An´lise do Problema . . a 2.2 Modelagem do Problema
2.2.1 Graham . . . . .
2.2.2 Quick Hull . . . .
2
.
.
.
.
2
2
2
2
2
3 Solu¸˜o Proposta ca 3.1 Id´ia Principal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . e 3
3
4 Algoritmo para o Convex Hull
4.1 Graham . . . . . . . . . . . .
4.2 Quick Hull . . . . . . . . . . .
4.3 Monotone Chain . . . . . . .
4.4 Divis˜o e conquista . . . . . . a 4.5 OUTRO . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
3
3
4
4
4
5 Algoritmos Paralelizado
5.1 Vari´veis, Estrutura e Registros a 5.2 Graham scan . . . . . . . . . .
5.2.1 Descri¸˜o do algoritmo . ca 5.2.2 Ordena¸˜o dos pontos . ca 5.3 Quick Hull . . . . . . . . . . . .
5.3.1 Descri¸˜o do Algoritmo . ca .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.