Exportar registro bibliográfico

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
  • Acesso à fonte
    How to cite
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • 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/

    Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2021