next up previous contents
Next: Varredura do Espaço Up: Técnicas Básicas Previous: Transformações Geométricas

Dualidade

 

Muitas estruturas possuem uma espécie de inversa, como os números reais, as matrizes, e etc. Esta dualidade, como é chamada, pode se apresentar de diversas formas. Suas caracterí sticas são tais que o dual de um objeto (primal) deve ter estrutura semelhante, e o dual do dual é o primal.

Esta técnica já é usada há muito tempo, por exemplo em programação linear, onde podemos resolver o problema dual ao invés do primal.

Aqui apresentaremos o Diagrama de Voronoi como sendo o dual da Triangulação\ de Delaunay. Normalmente o Diagrama de Voronoi é apresentado primeiro.

Se em cada circuncentro de cada triângulo da Triangulação de Delaunay for colocado um vértice, e entre cada par de novos vértices que estiverem em triângulos vizinhos, for colocada uma aresta coincidente com a mediatriz, teremos o Diagrama de Voronoi do conjunto de pontos iniciais.

Como visto na seção 2.2, o Diagrama de Voronoi divide o plano em regiões onde o ponto mais próximo de todos dentro de cada uma é o ponto inicial que está dentro dela.

O Diagrama de Voronoi é bastante útil, e pode ser encontrado facilmente através da Triangulação de Delaunay, em tempo linear, portanto preciso de tempo tex2html_wrap_inline2049 para achá-lo.

Outra dualidade interessante é a de polí gonos. Seja um polí gono P de vértices tex2html_wrap_inline2173 . O polí gono Dual(P), dual de P, é tal que seus vértices são tex2html_wrap_inline2179 , onde tex2html_wrap_inline2181 é o ponto da aresta tex2html_wrap_inline2183 mais próximo da origem (considere tex2html_wrap_inline2185 ), ou seja, tex2html_wrap_inline2181 é perpendicular à aresta tex2html_wrap_inline2183 com módulo igual a distância dela a origem.

Um resultado bastante surpreendente, que usa a dualidade é o seguinte:

Sejam P e Q dois polí gonos planares, Dual o operador de dualidade como descrito acima, e FC o operador de fecho convexo, então

displaymath2167

Este resultado nos diz que para calcular a intersecção de dois polí gonos, posso calcular o fecho convexo de seus duais, e depois dualizar. Como achar o dual é linear, temos uma relação entre intersecção de polí gonos e o fecho convexo no plano.


next up previous contents
Next: Varredura do Espaço Up: Técnicas Básicas Previous: Transformações Geométricas

Andre Luiz Pires Guedes
Fri Jun 14 17:05:55 EST 1996