<p>Entering the era of big data, human beings are faced with an unprecedented amount of geometric data today. Many computational challenges arise in processing the new deluge of geometric data. A critical one is data uncertainty: the data is inherently noisy and inaccuracy, and often lacks of completeness. The past few decades have witnessed the influence of geometric algorithms in various fields including GIS, spatial databases, and computer vision, etc. Yet most of the existing geometric algorithms are built on the assumption of the data being precise and are incapable of properly handling data in the presence of uncertainty. This thesis explores a few algorithmic challenges in what we call geometric computing over uncertain data.</p><p>We study the nearest-neighbor searching problem, which returns the nearest neighbor of a query point in a set of points, in a probabilistic framework. This thesis investigates two different nearest-neighbor formulations: expected nearest neighbor (ENN), where we consider the expected distance between each input point and a query point, and probabilistic nearest neighbor (PNN), where we estimate the probability of each input point being the nearest neighbor of a query point.</p><p>For the ENN problem, we consider a probabilistic framework in which the location of each input point and/or query point is specified as a probability density function and the goal is to return the point that minimizes the expected distance. We present methods for computing an exact ENN or an \\eps-approximate ENN, for a given error parameter 0 < \\eps < 1, under different distance functions. These methods build an index of near-linear size and answer ENN queries in polylogarithmic or sublinear time, depending on the underlying function. As far as we know, these are the first nontrivial methods for answering exact or \\eps-approximate ENN queries with provable performance guarantees. Moreover, we extend our results to answer exact or \\eps-approximate k-ENN queries. Notably, when only the query points are uncertain, we obtain state-of-the-art results for top-k aggregate (group) nearest-neighbor queries in the L1 metric using the weighted SUM operator.</p><p>For the PNN problem, we consider a probabilistic framework in which the location of each input point is specified as a probability distribution function. We present efficient algorithms for (i) computing all points that are nearest neighbors of a query point with nonzero probability; (ii) estimating, within a specified additive error, the probability of a point being the nearest neighbor of a query point; (iii) using it to return the point that maximizes the probability being the nearest neighbor, or all the points with probabilities greater than some threshold to be the nearest neighbor. We also present some experimental results to demonstrate the effectiveness of our approach.</p><p>We study the convex-hull problem, which asks for the smallest convex set that contains a given point set, in a probabilistic setting. In our framework, the uncertainty of each input point is described by a probability distribution over a finite number of possible locations including a null location to account for non-existence of the point. Our results include both exact and approximation algorithms for computing the probability of a query point lying inside the convex hull of the input, time-space tradeoffs for the membership queries, a connection between Tukey depth and membership queries, as well as a new notion of \\beta-hull that may be a useful representation of uncertain hulls.</p><p>We study contour trees of terrains, which encode the topological changes of the level set of the height value \\ell as we raise \\ell from -\\infty to +\\infty on the terrains, in a probabilistic setting. We consider a terrain that is defined by linearly interpolating each triangle of a triangulation. In our framework, the uncertainty lies in the height of each vertex in the triangulation, and we assume that it is described by a probability distribution. We first show that the probability of a vertex being a critical point, and the expected number of nodes (resp. edges) of the contour tree, can be computed exactly efficiently. Then we present efficient sampling-based methods for estimating, with high probability, (i) the probability that two points lie on an edge of the contour tree, within additive error; (ii) the expected distance of two points p, q and the probability that the distance of p, q is at least \\ell on the contour tree, within additive error and/or relative error, where the distance of p, q on a contour tree is defined to be the difference between the maximum height and the minimum height on the unique path from p to q on the contour tree.</p> / Dissertation

Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-06-10T11:28:09Z No. of bitstreams: 1 robertodecarvalhoferreira.pdf: 4632819 bytes, checksum: e5bd9a607a629a54c4f57e8d4c95a5ed (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-07-13T13:47:43Z (GMT) No. of bitstreams: 1 robertodecarvalhoferreira.pdf: 4632819 bytes, checksum: e5bd9a607a629a54c4f57e8d4c95a5ed (MD5) / Made available in DSpace on 2016-07-13T13:47:43Z (GMT). No. of bitstreams: 1 robertodecarvalhoferreira.pdf: 4632819 bytes, checksum: e5bd9a607a629a54c4f57e8d4c95a5ed (MD5) Previous issue date: 2012-08-29 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A evolução dos computadores, mais especificamente no que diz respeito ao aumento de sua capacidade de armazenamento e de processamento de dados, possibilitou a construção de ferramentas computacionais destinadas à simulação de fenômenos físicos e químicos. Com isso, a realização de experimentos práticos vem, em alguns casos, sendo substituída pela utilização de experimentos computacionais, que simulam o comportamento de inúmeros elementos que compõem o experimento original. Neste contexto, podemos destacar os modelos utilizados para a simulação de fenômenos em escala atômica. A construção desses simuladores requer, por parte dos desenvolvedores, um amplo estudo e definição de modelos precisos e confiáveis. Tal complexidade se reflete, muitas vezes, em simuladores complexos, destinados a simulação de um grupo restrito de estruturas, expressos de maneira fixa, utilizando algumas formas geométricas padrões. Este trabalho propõe uma ferramenta computacional para a geração de um conjunto de estruturas cristalinas. Este conjunto é caracterizado pela organização espacial regular dos átomos que a compõe. A ferramenta é composta por a) uma linguagem de programação, que rege a criação das estruturas através da definição de um sistema cristalino e a construção de objetos a partir de funções características e operadores CSG (Construtive Solid Geometry), e b) um compilador/interpretador que analisa um código fonte escrito na linguagem, e gera a partir deste o objeto correspondente. A ferramenta oferece aos desenvolvedores um mecanismo simples que possibilita a geração de um número irrestrito de estruturas. Sua aplicabilidade é demonstrada através da incorporação de uma estrutura, gerada a partir de um código fonte, ao simulador Monte Carlo Spins Engine, criado pelo Grupo de Computação Gráfica da Universidade Federal de Juiz de Fora. / The evolution of computers, more specifically regarding the increased storage and data processing capacity, allowed the construction of computational tools for the simulation of physical and chemical phenomena. Thus, practical experiments are being replaced, in some cases, by computational experiments that simulate the behavior of many elements that compose the original one. In this context, we can highlight the models used to simulate phenomena at the atomic scale. The construction of these simulators requires, by developers, the study and definition of accurate and reliable models. This complexity is often reflected in the construction of complex simulators, which simulate a limited group of structures. Such structures are sometimes expressed in a fixed manner using a limited set of geometric shapes. This work proposes a computational tool that aims to generate a set crystal structures. Crystal structures are characterized by a set of atoms arranged in a regular way. The proposed tool consists of a) a programming language, which is used to describe the structures using for this purpose characteristic functions and CSG (Construtive Solid Geometry) operators, and b) a compiler/interpreter that examines the source code written in the proposed language, and generates the objects accordingly. This tool enables the generation of an unrestricted number of structures. Its applicability is demonstrated through the incorporation of a structure, generated from the source code, to the Monte Carlo Spins Engine, a spin simulator developed by the Group of Computer Graphics of the Federal University of Juiz de Fora.