MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 818 6140

E-MAIL cef@ime.usp.br

Geometria Computacional

Primeira Lista de Exercícios - Entrega 15 de setembro de 1999

1.

Descreva um algoritmo $O(n\log n)$ para determinar se um polígono de n vértices é simples.

2.

Um disco consiste de uma circunferência e seu interior, e pode ser representado pelo seu centro e raio.
a. Descreva um algoritmo $O(n\log n)$ para verificar se dados n discos, dois deles se interceptam.
b. Você consegue descrever um algoritmo diferente para o caso em que todos os discos têm o mesmo raio? Qual a complexidade desse algoritmo?

3.

Dados n segmentos contendo um total de k interseções, mostre como encontrar todas as k interseções em tempo $O((n+k)\log n)$.