Instituto de Matemática Pura e Aplicada

Geometria Computacional - 2001

4a Lista de Exercícios

Para 22/5/2001

1. Suponha que uma subdivisão planar esteja representada através de uma estrutura de dados topológica (winged-edge ou DCEL).

1. Escreva um algoritmo que, dada uma face F, obtém seus vértices em tempo linear.
2. Escreva um algoritmo que, dado um vértice v, obtém todos os vértices adjacentes a v em tempo linear.

2. Generalize a relação de Euler (V + F – A = 2) para considerar o caso em que as regiões de uma subdivisão planar não têm necesariamente bordo conexo (isto é, podem também apresentar um total de R bordos internos).

3. Seja P um poliedro convexo do espaço tri-dimensional com n arestas (representado através de uma estrutura winged-edge), seja a uma de suas arestas e seja p um ponto exterior.

1. Descreva um teste para verificar se o plano definido por a e p é um plano de suporte de P (isto é, se P está contido em um dos semi-espaços definidos por este plano).
2. Qual a complexidade de se aplicar este teste a uma aresta de P? A todas as arestas de P?

4. O objetivo deste problema é estabelecer a fórmula de Pick para a área de um polígono. É necessário utilizar o seguinte fato, que não precisa ser demonstrado: um triângulo cujos vértices tem coordenadas inteiras não tem outros pontos de coordenadas inteiras em seu bordo ou interior se e somente se sua área é igual a 1/2.
   Seja P um polígono simples em que todos os vértices tem coordenadas inteiras. Seja I o número de pontos de coordenadas inteiras no interior do polígono e B o número de pontos de coordenadas inteiras no bordo do polígono (incluindo os vértices). No exemplo abaixo, I = 14 e B = 11.

(a) Mostre que a área de P é dada por . [Sugestão: tome uma triangulação do interior de P na qual os vértices sejam os pontos de coordenadas inteiras em seu bordo e seu interior.]

(b) A fórmula de Pick fornece um modo eficiente para se calcular a área de um polígono?