Bem-vindo!
Bem-vindo à MAC 331 / MAC 5747 Geometria Computacional. Esta é uma disciplina introdutoria em desenvolvimento e análise de algoritmos eficientes para problemas envolvendo objetos geométricos como pontos e retas, principalmente, em espaços de dimensão 2 e 3. Abaixo encontra-se uma descrição de alguns dos ingredientes principais desta disciplina.
A procura de algoritmos para resolver problemas geométricos vem desde a época da antiguidade. (Algumas motivações práticas para a busca por tais algoritmos foram os impostos sobre o uso da terra e construções de edificações.) São bem-conhecidas as construções geométricas de Euclides que usavam como instrumentos régua e compasso e consistiam de algumas operações primitivas que podiam ser realizadas com esses instrumentos. Um dos problemas algorítmicos em geometria foi o chamado Problema de Apollonius (cerca de 200 A.C.) no qual três circunferências arbitrárias no plano eram dadas e pedia-se uma quarta circunferência que fosse tangente às três circunferências dadas. Euclides apresentou um algoritmo que resolve este problema. (Diremos que um problema é algorítmico se este problema pede como resposta um algoritmo para resolver um determinado problema. Em geometria clássica esses problemas são conhecidos como Problemas de Construções Geométricas.)
Dentre todos os problemas algorítmicos em geometria (usando construções geométricas de Euclides) um que atraiu grande atenção foi o problema da construção de um polígono regular de n lados. Para alguns valores de n (e.g. n=3,4,5,6) a solução é conhecida desde a antiguidade. Entretanto, para heptágonos regulares (n=7) prova-se que o problema não tem solução. (Aos 17 anos Carl Friedrich Gauss (1777-1855) mostrou que não existe um algoritmo que usando somente as operações primitivas de Euclides construa um heptágono regular. Na realidade Gauss mostrou mais que isso, ele mostrou que existe um algoritmo para construir um p-gon (polígono regular com p lados), p primo se e somente se p é um primo da forma 2{2n}+1.)
Em 1902, Emile Lemoine introduziu uma medida de simplicidade para os algoritmos que usam as construções de Euclides. Esta medida é baseada no número de operações primitivas realizadas pelo algoritmo. Para Lemoine o algoritmo mais simples é aquele que faz menos operações primitivas. A solução de Euclides para o Problema de Apollonius requer 508 dessas operações enquanto que um algoritmo proposto por Lemoine requer menos de duzentas. Estava portanto introduzido em geometria um conceito que é, pelo menos em essência, o que hoje chamamos de complexidade de um algoritmo.
Em geometria computacional também estamos interessados em desenvolver algoritmos eficientes para resolvermos problemas geométricos. Pelo que foi exposto acima vemos que não é algo novo. A diferença é que as operações primitivas usam um instrumento diferente da régua e do compasso: usam um computador. Um pouco mais precisamente, em geometria computacional estamos interessados em encontrar algoritmos eficientes, ou procedimentos computacionais, para resolver problemas geométricos. Muitos desses problemas tem sua origem em outras áreas como computação gráfica, robótica, computer-aided design e processamento de imagens. No desenvolvimento de tais algoritmos são comumente utilizados resultados em geometria euclidiana, combinatória, teoria dos grafos, estruturas de dados e análise de algoritmos.
Geometria computacional é um termo usado por diversos grupos. (O termo ``geometria computacional'' tem sido usado com várias conotações distintas. Por exemplo, geometria computacional também foi usado para se referir a modelagem geométrica através de splines e superfícies (cf. Capítulo 1 de Preparata e Shamos [24]).) Entretanto, o termo tem sido mais utilizado para descrever a sub-área da teoria de algoritmos que trata do desenvolvimento e análise de algoritmos eficientes para problemas envolvendo objetos geométricos, principalmente, em espaços de dimensão 2 e 3, ou de dimensão constante. As entradas para os problemas são primordialmente objetos simples (pontos, retas, segmentos de retas, polígonos, planos, e poliedros). É neste último sentido que usaremos o termo geometria computacional nesta disciplina.
Se a tese de M.I. Shamos em 1978 (cf. [24]) for aceita como o início da geometria computacional (pelo menos da maneira como ela será tratada nesta disciplina, então a área tem apenas 22 anos. Apesar disso existem pelo menos 7 livros na área, 4 jornais.
A área desenvolveu rapidamente nos anos 70's, 80's e 90's, e ainda continua a se desenvolver. Por causa da área a partir da qual cresceu (desenvolvimento de algoritmos discretos), geometria computacional tem sempre enfatizado problemas de natureza matemática discreta. Na maioria dos problemas em geometria computacional as instâncias dos problemas são um conjunto finito de pontos ou outro objeto geométrico, e a saída exigida é algum tipo de estrutura consistindo de um conjunto finito de pontos ou segmentos de retas.
Se a tese de M.I. Shamos em 1978 (cf. [24]) for aceita como o início da geometria computacional (pelo menos da maneira como ela será tratada nesta disciplina, então a área tem apenas 19 anos. Apesar disso existem pelo menos 7 livros na área, 4 jornais.
De acordo com O'Rourke [21] (página xi):
``...Not all open problems [em geometria computacional] are necessarily difficult; some are simply awaiting the requisite attention ...''.Este pode ser um bom motivo para ficarmos de olhos abertos durante a disciplina e talvez tentar fazer alguma contribuição para a área.
[O que foi brevemente tratado nesta introdução foi extraído de Capítulo 3 de Courant [4], Graham [13], Mount [18], e no Capítulo 1 de Preparata e Shamos [23].]
O objetivo desta disciplina é apresentar técnicas, algoritmos e estruturas de dados empregados no desenvolvimento e análise de algoritmos eficientes para resolução de problemas geométricos. Pretendemos mostrar estratégias clássicas de solução de problemas geométricos, assim como apresentar possivelmente temas de pesquisa.
Cobriremos o ``background'' básico necessário para o estudo de geometria computacional. Este background incluirá resultados em geometria Euclidiana (dimensão 2 e 3), teoria dos grafos, e desenvolvimento e análise de algoritmos (i.e. contagem do número de operações primitivas feitas pelos algoritmos).
Para esta disciplina os pré-requisitos são: conhecimento de técnicas básicas de desenvolvimento de algoritmo, como divisão-e-consquista, algoritmo guloso, programação dinâmica; técnicas básicas de análise de algoritmos como notação assintótica, resolver somatórias e relações de recorrência; e conhecimento de estruturas de dados básicas como heap e árvores balanceadas de busca binária.
A nota final na disciplina será baseada em três componentes:
O projeto valerá 25% da nota final.
Na página
http://www.ime.usp.br/~coelho/mac747/projetos.html,vocês podem ver os projetos do pessoal que cursou a disciplina no 2o. semestre de 1997.
Alguns dos tópicos que pretendemos cobrir nesta disciplina são: fechos convexos; problemas de proximidade; partições convexas; busca geométrica; e problemas de intersecção.
Abaixo encontra-se uma breve descrição de alguns desse tópicos.
O Problema do par mais próximo (The closest pair problem)
Dados n pontos queremos encontrar dois cuja distância entre eles é mínima. Uma aplicação prática deste problema é em controle de tráfego aéreo: os dois aviões que estão em maior perigo de colisão são aqueles que estão mais próximos. Este problema pode ser resolvido facilmente em O(dn2) onde d é a dimensão do espaço. O problema do par mais próximo pode ser resolvido por um algoritmo do tipo divisão-e-conquista em tempo O(dn log n) (cf. Capítulo 5 de Preparata e Shamos [23]) .
Fecho convexo de um conjunto de pontos
Convexidade é uma propriedade geométrica bastante importante. Um conjunto de pontos é convexo se para cada par de pontos no conjunto, o segmento de reta entre eles está inteiramente contido no conjunto. Segundo O'Rourke (cf. O'Rourke [21], pg. 80) talvez o primeiro artigo na área de geometria computacional tenha sido sobre fechos convexos. O Problema do Fecho Convexo consiste em: dados: n pontos; encontrar: o fecho convexo desses pontos. Uma aplicações práticas deste problema se encontra em robótica. Se o fecho convexo de um robô não colide com obstáculos então o robô também não colide.
Nos anos 60 uma aplicação da Bell Labs necessitava computar o fecho convexo de aproximadamente 10.000 pontos no plano e os algoritmos de complexidade de tempo O(n2) foram considerados muito lentos. Tendo essa aplicação como motivação, no começo do anos 70, Graham [12] desenvolveu o primeiro algoritmo de complexidade de tempo O (n log n). O fecho convexo também pode ser construído em tempo O (n log n) por um algoritmo de divisão-e-conquista (cf. Capítulo 3 de Preparata e Shamos [23]).
Triangularização de polígonos
O interesse aqui é particionar um certo `domínio complexo' em uma coleção de objetos `simples'. A região mais simples na qual podemos decompor um objeto planar é um triângulo (um tetraedro em 3-d e um `simplex' em geral). Dado um polígono P queremos adicionar o maior número possível de diagonais (que não se cruzem) a P de tal forma que o interior do polígono fique particionado em triângulos. Chazelle [1] desenvolveu um algoritmo linear para este problema.
Um algoritmo para triangularizar polígonos pode ser utilizado em problemas do tipo Art Gallery (cf. O'Rourke [20]). Imagine que as salas de uma galeria de arte formem um polígono. Qual é o menor número de guardas que são necessários para tomarem conta das salas. Estamos consideramos que cada guarda fique parado em um local da galeria.
Partição de polígonos
Além de algoritmos eficientes para particionar um polígono em triângulos, também é de interesse o desenvolvimento de algoritmos que particionem um polígono em (digamos) polígonos monótonos, trapezóides e polígonos convexos. Uma motivação para particionar um polígono em polígonos convexos é reconhecimento de caracteres: um caractere pode ser representado como um polígono particionado em partes convexas.
Intersecções
Um dos problemas geométricos mais básicos é o de determinar quando dois objetos se intersectam. A determinação se dois objetos complexos se intersectam é frequentemente reduzida ao problema de determinar quais pares de entidades primitivas (e.g., segmentos de retas) se intersectam. Veremos algoritmos eficientes para computar a intersecção de um conjunto de segmentos de retas.
Diagramas de Voronoi
Dado um conjunto S de n pontos no plano queremos determinar para cada ponto p em S qual é a região V(p) dos pontos do plano que estão mais perto de p do que de qualquer outro ponto em S. As n regiões V(p) formam uma partição do plano chamada de Diagrama de Voronoi.
Imagine uma vasta floresta contendo vários pontos de observação de incêndio. O conjunto das árvores que estão mais próximas de um determinada posto p determina a região V(p) das árvores que são de responsabilidade de ponto p.
O diagrama de Voronoi de um conjunto de n pontos pode ser contruído em tempo O(n \log n) por um (complicado) algoritmo do tipo divisão-e-conquista (cf. Shamos [25]). Em 1985, Fortune [10] desenvolveu um algoritmo de varredura (plane-sweep algorithm) muito elegante e simples cuja complexidade de tempo é O(n \log n).
Triangularização de Delaunay
O dual geométrico (usando retas) de um diagrama de Voronoi para um
conjunto S de pontos forma uma triangularização do conjunto S,
chamada de triangularização de Delaunay. A triangularização de
Delaunay tem várias propriedades geométricas interessantes, por exemplo,
ela contém todas as ``árvores
geradoras mínimas'' de S (cf. Capítulo 6 de Preparata e Shamos [23]).
Arranjos e dualidade
Talvez uma das estruturas matemáticas mais importantes em geometria computacional seja arranjo de retas (e em geral, arranjos de curvas e superfícies). Dadas n retas no plano, um arranjo é simplesmente o grafo que tem como vértices as intersecções das retas e como as aretas os segmentos de retas ligando estas intersecções. Veremos que uma tal estrutura pode ser construída em tempo O(n2). A razão para está estrutura ser tão importante é que muitos problemas envolvendo pontos podem ser transformados em problemas envolvendo retas através do método de dualidade. Por exemplo, suponha que desejemos determinar se existem três pontos colineares entre um conjunto de n pontos no plano. Isto pode ser determinado por um algoritmo do tipo força-bruta em tempo O(n3). Entretanto, se os pontos são dualizados em retas, então (como veremos mais tarde nesta semestre) a questão é reduzida a decidir se existe um vértice de grau pelo menos 4 neste arranjo de retas.
Para preparar as aulas desta disciplina tenho consultado as notas de aula de Ferreira [8], Godfried [11], Guibas [14], Khuller [16], Mount [18], Pemmaraju [22], junto com alguns livros e artigos.
O livro de Preparata e Shamos [23] é um texto clássico em geometria computacional (foi primeiro livro sobre o assunto) que coloca bastante ênfase na análise dos algoritmos apresentados. Este livro contém basicamente todos os tópicos que serão tratados nesta disciplina. Outros livros que também podem ser encontrados na biblioteca são: Edelsbrunner [7] (``The art of counting and estimating is at heart of combinatorics--and it is a necessary prerequisite for analyzing algorithms ...''; cópiado da introdução da Parte I de [7]); Figueiredo e Carvalho [9] (um livro muito claro e introdutório); e Resende e Stolfi [6] (descreve varias técnicas e algoritmos em geometria computacional). Outros livros sobre geometria computacional são: O'Roukey [21] (este livro da mais enfase ao desenvolvimento dos algoritmos e, de certa forma, menos atenção à análise); Laszlo [17] (um livro que descreve vários algoritmos em geometria computacional e apresenta trechos de implementações em C++); Mulmuley [19] (como o próprio título diz, este livro trata de algoritmos aleatórios em geometria computacional). M. de Berg, M. van Kreveld, M. Overmars, e O. Schwarzkopf [5] (parece que este livro é muito bom, mas eu nunca vi, estou esperando sair a segunda edição para compra-lo).
Cormen, Leiserson & Rivest [3] é um livro enciclopédico sobre análise de algoritmos que trata de geometria computacional no Capítulo 35.
Na biblioteca também podem ser encontrados alguns surveys sobre geometria computacional, veja por exemplo: Chazelle [2]; Graham e Yao [13]; Guibas e Stolfi [15]; e Yao [26].
Artigos em geometria computacional podem ser encontrados em várias revistas, incluindo ACM Transactions on Graphics, Algorithmica, Journal of Algorithms, Journal of the ACM, e SIAM Journal on Computing. Uma revista que é particularmente dedicada à área é Discrete and Computational Geometry e mais recentemente temos International Journal of Computational Geometry & Applications e Computational Geometry, Theory and Applications.
Existe uma conferência anual em geometria computacional a ACM Annual Conference on Computational Geometry (alguns dos proceedings podem ser encontrados na biblioteca; veja QA758.C S989). Outras conferências que também apresentam trabalhos em geometria computacional são STOC (QA800.C S989), FOCS (QA800.C S989), SODA (QA758.C S989), e ICALP. Alguns professores do Departamento de Ciência da Computação (como o prof. José Augusto, sala A-302, e-mail jose@ime.usp.br) podem ter alguns proceedings que a biblioteca não tem.
Algumas das implementações que vocês verão durante as aulas foram feitas por Cassio Polpo de Campos (e-mail cassio@ime.usp.br e URL http://www.ime.usp.br/~cassio/) e Eduardo Garcia de Freitas (e-mail freitas@ime.usp.br e URL http://www.ime.usp.br/~freitas/). O Cassio fez suas implementações no Turbo C e o Eduardo fez applets em Java. Todos os programas estão disponíveis no URL
http://www.ime.usp.br/~freitas/gc/.
Existe muito material muito bom de Geometria Computacional na Internet. Durante o andamento da disciplina estarei mantendo, na página
http://www.ime.usp.br/~coelho/geocomp2000/sitios/,uma lista de alguns sítios de Geometria Computacional. Durante o andamento da disciplina está página deverá ser atualizada e expandida. Se você encontrar algum sítio de Geometria Computacional (ou de qualquer outra coisa) que você ache interessante, por favor, não deixe de me avisar.
O monitor desta disciplina é Fabio H. Viduani Martinez, sala B-141, e-mail fhvm@ime.usp.br.
A minha sala é a B-164, o número do meu telefone é 818-6295 e meu endereço eletrônico é coelho@ime.usp.br.
Manterei uma página de MAC 331 / MAC 5747 no URL
http://www.ime.usp.br/~coelho/geocomp2000/.Nessa página eu colocarei o material da disciplina (como, por exemplo, listas de exercícios). Por favor, dê uma olhada nesta página regularmente.
Estarei mantendo uma lista de discussão que tem como objetivo servir de suporte para a disciplina. Recomenda-se que você mande para esta lista suas dúvidas, sugestões, críticas ou observações sobre o andamento da disciplina. Assim, se você pretende cursar geometria computacional, por favor, veja a página
http://www.ime.usp.br/~coelho/geocomp2000/lista/e inscreva-se na lista de discussão. Sinta-se a vontade para me escrever e fazer perguntas ou comentários sobre a disciplina.
Outros professores do Departamento de Ciência da Computação que estudam geometria computacional são Carlos Eduardo Ferreira (sala A-297, e-mail cef@ime.usp.br) e José Augusto Ramos Soares (sala B-126, e-mail jose@ime.usp.br).
Se você se interessa por Computação Gráfica converse com o professor Antonio Elias Fabris (sala B-112 , e-mail aef@ime.usp.br). Agora, se você quer saber o que é Processamento de Imagens, Visão Computacional ..., então bata um papo com os professores Carlos Hitoshi Morimoto (sala A-300, e-mail hitoshi@ime.usp.br), Júnior Barreira (sala A-290, e-mail jb@ime.usp.br), e Roberto Marcondes Cesar Júnior (sala A-297, e-mail cesar@ime.usp.br).