Busca em subespaços em varias dimensões

Orientador: Pedro Jussieu de RezendeDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da ComputaçãoResumo: o tema central deste trabalho é a pesquisa de soluções para problemas de busca em subespaços (range search), sob o enfoque de projeto de algoritmos eficientes e geometria computacional, considerando objetos de dados em forma de pontos dispersos num espaço multidimensional e explorando diversos formatos de subespaços de busca encontrados na literatura. O objetivo é reunir diversas formulações e métodos de solução em um compêndio, onde estes são descritos sob uma mesma ótica, com notação uniforme e de forma mais simples que nos textos originais, de modo a facilitar um estudo mais detalhado e comparações, no que diz respeito à natureza e ao funcionamento das soluções. Pretende-se com isso tornar as idéias provenientes da pesquisa atualmente em processo na área de algoritmos acessíveis de forma mais integrada e simples, tanto aos interessados na pesquisa de métodos mais eficientes e adequados para problemas em teoria da computação, quanto àqueles mais interessados na aplicação dessas idéias. Um estudo abrangente das soluções encontradas na literatura permite perceber diversas semelhanças de concepção nos métodos empregados. Freqüentemente, pode-se observar a ocorrência de abordagens e técnicas comuns em diversas situações. A estas abordagens e técnicas de aplicação geral atribuímos o nome de paradigmas de algoritmos. O estudo e a utilização de paradigmas de algoritmos possibilitam um certo grau de sistematização das soluções de problemas de busca em subespaços, uma vez que eles permitem encarar diversas soluções distintas, de diversas variações do problema como manifestações de um mesmo fundamento racional. Alem disso, o estudo de paradigmas é instrutivo, pois promove o desenvolvimento de raciocínios sistemáticos, aplicáveis na resolução de diversos problemas em computação. A divisão do conteúdo é efetuada de maneira a fornecer primeiro o fundamento: teórico, necessário à compreensão dos métodos de solução, que são tratados posteriormente. No capítulo 1, são fornecidos os conceitos e classificações básicos, relativos a problemas de busca em geral e particularmente busca em subespaços, a fim de prover uma fundamentação teórica e situar a área de estudo.. No capítulo 2, são descritos alguns paradigmas de algoritmos aplicados a problemas de busca em subespaços, com o intuito de prover ao leitor maneiras alternativaS de relacionar as soluções apresentadas posteriormente, induzindo-o a desenvolver raciocínios que lhe habilitem a perceber os fundamentos e técnicas em comum. Nos capítulos 3 a 6, são abordados os sub.problemas caracterizados pelos formatos clássicos de subespaços de busca encontrados na literatura, ordenados da maneira que parece mais conveniente e que reflete a complexidade das soluções, a natureza das mesmas e sua evolução histórica. Em cada um destes capítulos, os sub-problemas são discutidos em detalhes, algumas soluções e limites inferiores são descritos superficialmente e há uma seção de notas bibliográficas, com referências para assuntos específicos. Finalmente, no capítulo 7, são sintetizadas as contribuições do trabalho e relacionados alguns assuntos para possíveis extensões no futuro.Abstract: The main, objective of this work is the study of solutions found in the literature to range search, from the view point of algorithm design and computational geometry, considering only data objects; in the form of points embedded1 in a multidimensional space, and investigating various shapes of ranges. Several formulations and solutions to range search problems are surveyed. These are described under one abstract view, with uniform notation and in a form hopefully clearer than, the original sources, in such way that comparisons of the nature and functionality of the solutions and more detailed studies may be facilitated. Our purpose is to make the ideas deriving from the research on range search available in a more integrated and simpler way, to people interested in the discovery of more suitable and. efficient methods for problems in theoretical computer science as well as to those interested in the applications of these ideas. A wide study of the solutions found in the literature shows many conceptual similarities in the employed methods. Frequently, the same approaches and' techniques are seen in distinct situations. These general purpose approaches and techniques are called "algorithm paradigms". The study and application of these paradigms allow a certain level of generalization of the solutions to range search problems, because they allow one to perceive several solutions of vario1ls instances of a general problem as the manifestation of the same rationale. The study of algorithm paradigms is instructive in its own right, since it propitiates the development of systematic reasoning, useful in the solution of many problems in computer science. The contents herein are arranged so as to first give the theoretical basis necessary to understanding the methods given later. In chapter 1, we provide the basic concepts and classifications related to search problems in general and to range search in particular, and establish the scope of our research. In chapter 2, we describe some algorithm paradigms applied to range search problems, with the purpose of supplying the reader with alternative ways of establishing connections among the solutions presented later leading him to develop a reasoning that allows the identification of the fundamentals and techniques shared by tile sol1itions. In, chapters 3 to 6, we deal with the variations of' the range search problem characterized by the classical shapes of ranges considered in the literature. These chapters are arranged in a convenient way in order to reflect the complexity ofthe discussed solutions, their nature and the historical evolution. In each one of these chapters the problems are discussed in detail, some solutions and lower bounds are briefly described and bibliographic notes containing references to specific subjects are presented. Finally, in chapter 7, we summarize the contributions of this work and extensions that can be undertaken in the future.MestradoMestre em Ciência da Computaçã