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. Consultas de segmentos em janelas: algoritmos e estruturas de dados. 2009. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2009. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-09122009-145514/. Acesso em: 24 fev. 2026. -
APA
Franco, Á. J. P. (2009). Consultas de segmentos em janelas: algoritmos e estruturas de dados (Dissertação (Mestrado). 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. Consultas de segmentos em janelas: algoritmos e estruturas de dados [Internet]. 2009 ;[citado 2026 fev. 24 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-09122009-145514/ -
Vancouver
Franco ÁJP. Consultas de segmentos em janelas: algoritmos e estruturas de dados [Internet]. 2009 ;[citado 2026 fev. 24 ] 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
