Geometria Computacional
Prof. Walter Mascarenhas
Segundo semestre de 2004
Aula 9
Decomposição em partes convexas
Convexo =
simples
Não convexo =
complexo
Ser convexo é:
Ter ângulos Ter Pontos internos
Ser intersecção
internos <= ligados por segmentos
de semiplanos
180
internos
Primeira tentativa: triangulação.
Custo baixo: teórico O(n). Esperado O(n log*n) na prática.
Qualidade: ruim, n - 2 partes
Segunda tentativa: juntar triângulos
(Hertel and Mehlhorn).
Custo baixo: teórico O(n). Esperado O(n log*n) na prática.
Qualidade: 2 r + 1 partes, r = número de ângulos reversos
Hertel and Mehlhorn: juntar quais triângulos?
Analise o “V” pontilhado associado
a cada vértice reverso.
1- Se o “V” contiver diagonais,
escolha uma delas e pinte-a de
magenta.
2- Se o “V” não contiver diagonal
alguma, pinte a diagonal mais
próxima do “V” de cada lado de
magenta.
3- Apague as diagonais que não
foram pintadas de magenta.
Hertel and Mehlhorn: resultado final
Número de diagonais
<= 2 r implica em número
de faces <= 2 r + 1.
Neste caso é melhor:
r = 4 e nFaces = 7 < 9
Poderia ser melhor?
Hertel and Mehlhorn: resultado final
Número de diagonais
<= 2 r implica em número
de faces <= 2 r + 1.
Neste caso é melhor:
r = 4 e nFaces = 7 < 9
Poderia ser melhor?
Pode melhorar? Sim, escolha outra triangulação:
Poderia ser ainda
melhor?
Pode melhorar? Só com diagonais não.
Pode
melhorar?
Pode melhorar? De jeito nenhum!
Prova: cada “V” pontilhado tem que conter
pelo menos um lado de uma parte convexa.
Como os “V”s pontilhados são disjuntos,
eles devem conter pelo menos 4 lados. Isto
implica em pelo menos 5 partes convexas.
Casos gerais
Teorema: é sempre possível obter r + 1 partes convexas.
Prova: trace as bissetrizes dos vértice reversos, uma a uma. As r
bissetrizes vão levar a r + 1 partes convexas.
Teorema: o número mínimo de faces convexas é r/2 + 1.
Prova: cada vértice reverso tem que ser “quebrado” pelo menos
uma vez. Uma diagonal quebra no máximo 2 vértices. Logo pelo
menos r/2 diagonais deverão permanecer. Isto dá r/2 + 1 faces.
Corolário: O algoritmo de Hertel & Mehlhorn erra por um fator de
no máximo 4 ~ (2 r + 1) / (r/2 + 1).
Exemplos: pontos internos
Hertel and Mehlhorn pode atingir o fator 4:
Hertel and Mehlhorn pode atingir o fator 4:
Uma proposta de algoritmo O(n logn) que erra no
máximo um fator de 2
Uma proposta de algoritmo O(n logn) que erra no
máximo um fator de 2
Estruturas de dados
1- Array de listas duplamente ligadas para representar os
polígonos em construção
2- Heap para determinar a o ordem dos eventos
3- Árvore balanceada para administrar os cortes da
scanline
Uma proposta de algoritmo O(n logn) que erra no
máximo um fator de 2. Eventos: novo lado
Uma proposta de algoritmo O(n logn) que erra no
máximo um fator de 2. Eventos: novo máximo local
Uma proposta de algoritmo O(n logn) que erra no
máximo um fator de 2. Eventos: novo mínimo local
Uma proposta de algoritmo O(n logn) que erra no
máximo um fator de 2. Evento: lado cruza V
Uma proposta de algoritmo O(n logn) que erra no
máximo um fator de 2. Evento: V cruza V