Windowing queries: algorithms and data structures. / Consultas de segmentos em janelas: algoritmos e estruturas de dados

AUTOR(ES)

Alvaro Junio Pereira Franco

DATA DE PUBLICAÇÃO

2009

RESUMO

In this work we study problems about point and segment query in rectangular windows whose edges are parallel to the axis. Given a set of segments (or points) in the plane. In a first phase these segments are organized in data structures such that queries for segments in windows are done more efficiently. In the second phase windows are given online. The data structures are balanced trees as range tree, priority search tree, interval tree and segment tree. In this masters thesis we show in details data structures and algorithms for solving windowing queries to sets of points (unidimensional version of the problem) and of segments in the plane, as horizontal and vertical as any orientation (without crossings). The algorithms are analysed rigorously regarding their space and time used. We implement the algorithms studied, building a library of these data structures. Finally, we present, the results of computational experiments with instances of the problem.

ASSUNTO(S)

windowing queries computational geometry data structures segment trees árvores de segmento algoritmos algorithms consultas em janelas estrutura de dados geometria computacional

Documentos Relacionados

• Estruturas de dados eficientes para algoritmos evolutivos aplicados a projeto de redes
• Evolutionary algorithms, to proteins structures prediction
• Reinforced concrete structures optmization using genetic algorithms.
• Otimização paramétrica de estruturas treliçadas por algoritmos genéticos
• Otimização de estruturas de materiais compósitos laminados utilizando algoritmos genéticos