Consultas de segmentos em janelas: algoritmos e estruturas de dados (2009)
- Authors:
- Autor USP: FRANCO, ÁLVARO JUNIOR PEREIRA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: ALGORITMOS E ESTRUTURAS DE DADOS; GEOMETRIA COMPUTACIONAL
- Agências de fomento:
- Language: Português
- Abstract: Neste trabalho estudamos problemas relacionados com a busca de pontos e segmentos em janelas retangulares com os lados paralelos aos eixos. É dado um conjunto de segmentos (ou pontos) no plano. Em uma primeira fase estes segmentos são organizados em estruturas de dados de tal forma a tornar buscas por aqueles que estão contidos em janelas retangulares mais eficientes. Na segunda fase são dadas as janelas de maneira online. Várias destas estruturas de dados são baseadas em áervores balanceadas, tais como árvore limite, árvore de busca com prioridade, árvore de intervalos e árvore de segmentos. Na dissertação mostramos detalhadamente estas estruturas de dados e os algoritmos para resolver este problema para conjuntos de pontos (versão unidimensional do problema) e para segmentos no plano, tanto horizontais e verticais como com qualquer orientação (sem cruzamentos). Os alforitmos são analisados de forma rigorosa quanto ao seu uso de espaço e de tempo. Implementamos também os vários algoritmos estudados, construindo uma biblioteca destas estruturas de dados. Apresentamos, finalmente, os resultados de experimentos computacionais com instâncias do problema.
- Imprenta:
- Data da defesa: 06.07.2009
-
ABNT
FRANCO, Álvaro Junio Pereira; FERREIRA, Carlos Eduardo. Consultas de segmentos em janelas: algoritmos e estruturas de dados. 2009.Universidade de São Paulo, São Paulo, 2009. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-09122009-145514/ >. -
APA
Franco, Á. J. P., & Ferreira, C. E. (2009). Consultas de segmentos em janelas: algoritmos e estruturas de dados. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-09122009-145514/ -
NLM
Franco ÁJP, Ferreira CE. Consultas de segmentos em janelas: algoritmos e estruturas de dados [Internet]. 2009 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-09122009-145514/ -
Vancouver
Franco ÁJP, Ferreira CE. Consultas de segmentos em janelas: algoritmos e estruturas de dados [Internet]. 2009 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-09122009-145514/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
