CC443: Algoritmos Geométricos

Sumários - Aulas Teóricas (2007/08)

Ana Paula Tomás

Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto


25/02/2008
Breve introdução à disciplina: Exemplos de alguns problemas (vigilância, geração de objectos geométricos, decomposição de objectos, triangulação). Teorema da Galeria de Arte (Chvátal, 1975). Algoritmos para construção de polígonos ortogonais: método "Dilatar-Cortar" (Tomás, Bajuelos 2004).

28/02/2008
Algoritmos para construção de polígonos ortogonais (cont.): métodos "Dilatar-Cortar" e "Dilatar-Colar" (Tomás, Bajuelos 2004).

03/03/2008
Varrimentos no plano: noção de linha de varrimento, estado da linha de varrimento e eventos. Aplicação de varrimento para determinação de partições de polígonos ortogonais por extensão das arestas incidentes em vértices reflexos: (i) vertical, (ii) horizontal, (iii) horizontal e vertical.

Aula Prática: Geração de polígonos por aplicação do método "Dilatar-Colar": análise do sub-problema da determinação da região rectangularmente-visível dum ponto (vértice convexo do polígono) usando a técnica de varrimento.

06/03/2008
Noção de conjunto convexo e invólucro convexo dum conjunto. Algoritmos para determinação de invólucros convexos no plano e sua complexidade: por varrimento rotacional (algoritmo de Graham e algoritmo de Jarvis ("gift wrapping")) e algoritmos baseados em dividir para conquistar (realização da junção em tempo linear baseada na determinação de tangentes inferiores e superiores). Algoritmos incrementais.

10/03/2008
Conclusão da aula anterior (breve referência ao algoritmo "Quick Hull", S. Aki e G. Toussaint, 1978).
Fórmula da área de um polígono (ideia duma demonstração).
Determinação de todos os pontos de intersecção dum conjunto de segmentos baseada em varrimento.

Aula Prática: introdução do problema de determinação de redes mínimas de Manhattan.

13/03/2008
Intersecção de segmentos: verificação da existência de alguma intersecção em O(n ln n) para n segmentos [Shamos & Hoey 1975]; determinação de todos os pares de segmentos que se intersectam em O((n+k) ln n), sendo k o número de pares [Bentley & Ottmann 1979] (algoritmo output sensitive)

(Férias de Páscoa: 17/03/2008 a 24/03/2008)

27/03/2008
Conclusão da aula anterior.

31/03/2008
Lista de arestas duplamente ligadas (DCEL): vértices, faces e arestas (semi-arestas, arestas gémeas), semi-arestas que delimitam face, navegação na estrutura (relação de adjacência).

Aula Prática: construção duma DCEL para representação da partição horizontal dum polígono ortogonal (sem arestas colineares).

03/04/2008
Sobreposição de mapas (com informação temática). Construção da DCEL obtida por sobreposição (i.e., junção) dum par de DCEL's em O(n log n + k log n), sendo n a complexidade das DCELs originais e k a da final.
Aplicação desse método para determinar a união, intersecção e diferença de polígonos (caso não convexo).

07/04/2008
Arranjos de rectas. Construção da DCEL para arranjo de n linhas em tempo O(n^2).
Triangulação. Orelhas e bocas em polígonos simples [Meisters, 1975, Toussaint, 1991]. Triangulação de polígonos por corte de orelhas. Teorema de Meisters, 1975 (análise do artigo original).
Número de triângulos de qualquer triangulação dum poligono simples com n vértices, valor da soma dos ângulos internos dum tal polígono. Grafo dual da triangulação (estrutura de árvore).

10/04/2008
Problemas de vigilância. Teorema da Galeria de arte [Chvatal] (recordar prova de Fisk).
Determinação do número mínimo de guardas necessário para vigiar um dado polígono simples (ref. complexidade NP-hard). Discretização do problema através da decomposição do polígono. Aproximação da solução óptima ppor refinamento da partição. Dominância entre regiões e dominância entre guardas. Exploração da noção de dominância na redução do modelo. [Tomás, Bajuelos, e Marques, AI&MATH2006]
Determinação da região de visibilidade dum ponto em O(n), com base no algoritmo de Lee [D.T.Lee, 1983] [B. Joe and R. B. Simpson, BIT, 1987]. Ideia do algoritmo.

14/04/2008
Reunião da FCUP com Assembleia Estatutária da Universidade do Porto (RJIES) (Não houve aula)

17/04/2008
Polígonos monótonos. Triangulação de polígonos monótonos em O(n). Decomposição de polígono simples em trapézios (possivelmente degenerados) e em polígonos monótonos. Determinação de triangulação em O(n log n) [D. Johnson M. Garey, F. Preparata, and R. Tarjan, 1978]: descrição do algoritmo. Existência de algoritmos lineares, isto é com complexidade O(n) [Chazelle, 1991] (óptima). Partição dum polígono simples em polígonos convexos (distinta de triangulação), por junção de triângulos adjacentes numa triangulação previamente construída.

21/04/2008
Algoritmos O(n log n) para determinação dum par de pontos a distância mínima e dum par de pontos a distância máxima num conjunto de n pontos do plano. Algoritmo para verificação da posição dum ponto relativamente a um polígono simples (exterior, interior, fronteira).

24/04/2008
Diagramas de Voronoi: propriedades, algoritmo para construção do diagrama de Voronoi de n pontos em O(n log n) baseado em dividir-para-conquistar [Shamos & Hoey 1975].

28/04/2008
Diagrama de Voronoi de n pontos: construção pelo algoritmo de Fortune (1986).

(Semana da Queima das Fitas: 05/05/2008 e 07/05/2008)

12/05/2008
Triangulação de Delaunay dum conjunto de n pontos (no plano): construção a partir do grafo dual do diagrama de Voronoi; propriedades: triangulação que maximiza o vector dos ângulos; construção da triangulação de Delaunay a partir duma triangulação qualquer por troca de arestas (edge-flipping); algoritmo para construção incremental (por inserção ponto a ponto; decomposição de triângulos por inserção do novo ponto; manutenção de informação histórica sobre a triângulação para resolução eficiente de problemas de localização de pontos).
Aplicação à construção de árvores euclideanas mínimas.

15/05/2008
(Dia da FCUP -- tolerância de ponto)

19/05/2008
Conclusão da aula anterior.
Problemas de localização de pontos: decomposição trapezoidal associada a um conjunto de n segmentos de recta (cujos interiores não se intersectam); algoritmo para construção duma estrutura de dados eficiente para a localização de pontos nesses regiões (localização em tempo médio O(log n) por ponto). [bibliografia: O'Rourke, sec. 7.11.4]

26/05/2008
Problemas de localização (cont): construção de kd-trees e de range trees para conjuntos de pontos; localização em regiões ortogonais k-dimensionais (intervalos, rectângulos, paralelipípedos, etc).

29/05/2008
Conclusão da aula anterior.
Breve revisão da matéria dada.