Instituto de Matemática Pura e Aplicada

Geometria Computacional - 2001

3a Lista de Exercícios

Para 8/5/2001

1. Sejam p₁, p₂, ..., p_n pontos do plano. Descreva um algoritmo linear que determina se p₁ é um vértice do fecho convexo de { p₁, p₂, ..., p_n }.
   [Sugestão: p₁ é vértice de conv{ p₁, p₂, ..., p_n } se e só se existe uma reta r contendo p₁ tal p₂, ..., p_n estejam no mesmo semiplano determinado por r.]
   
2. Implemente um algoritmo para encontrar o fecho convexo de um conjunto de pontos do plano. Diga a razão para a sua escolha (algoritmo mais fácil de implementar, algoritmo mais eficiente, algoritmo mais fácil de entender, etc). Teste o seu algoritmo com os seguintes conjuntos de pontos:

1. {(0, 0), (1, 1), (–3, 1), (–5, –2), (–4, –1), (3, 4), (2, 5), (1, 7), (–5, 0), (–1, –1)}
2. um conjunto de 20 pontos aleatórios, gerados independentemente de acordo com uma distribuição de probabilidade uniforme no quadrado unitário.

3. a) O que ocorre quando se aplica o algoritmo de Graham a um polígono simples? Sob que condições ele funciona corretamente? Dê exemplo de um polígono simples para o qual o algoritmo falha e um exemplo de um polígono simples não estrelado para o qual ele funciona corretamente.

b) O que ocorre quando se aplica o algoritmo de Graham a um polígono estrelado mas não se parte de um vértice do fecho convexo?

4. Sejam v_i–1, v_i, v_i+1 três vértices consecutivos de um polígono convexo.

1. Diga como estabelecer se o polígono tem orientação horária ou anti-horária.
2. Seja u um ponto do plano exterior ao polígono convexo. Diga como determinar se uv_i é uma reta de suporte de P (isto é, "tangente" a P).