<p>This thesis explores how to sparsely represent distributions of points for geometric statistical problems. A <italic>coreset<italic> C is a small summary of a point set P such that if a certain statistic is computed on P and C, then the difference in the results is guaranteed to be bounded by a parameter &epsilon;. Two examples of coresets are &epsilon;-samples and &epsilon;-kernels. An &epsilon;-sample can estimate the density of a point set in any range from a geometric family of ranges (e.g., disks, axis-aligned rectangles). An &epsilon;-kernel approximates the width of a point set in all directions. Both coresets have size that depends only on &epsilon;, the error parameter, not the size of the original data set. We demonstrate several improvements to these coresets and how they are useful for geometric statistical problems.</p><p>We reduce the size of &epsilon;-samples for density queries in axis-aligned rectangles to nearly a square root of the size when the queries are with respect to more general families of shapes, such as disks. We also show how to construct &epsilon;-samples of probability distributions. </p><p>We show how to maintain &ldquo;stable&rdquo; &epsilon;-kernels, that is if the point set P changes by a small amount, then the &epsilon;-kernel also changes by a small amount. This is useful in surveillance tracking problems and the stable properties leads to more efficient algorithms for maintaining &epsilon;-kernels. </p><p>We next study when the input point sets are uncertain and their uncertainty is modeled by probability distributions. Statistics on these point sets (e.g., radius of smallest enclosing ball) do not have exact answers, but rather distributions of answers. We describe data structures to represent approximations of these distributions and algorithms to compute them. We also show how to create distributions of &epsilon;-kernels and &epsilon;-samples for these uncertain data sets. </p><p>Finally, we examine a spatial anomaly detection problem: computing a spatial scan statistic. The input is a point set P and measurements on the point set. The spatial scan statistic finds the range (e.g., an axis-aligned bounding box) where the measurements inside the range are the most different from measurements outside of the range. We show how to compute this statistic efficiently while allowing for a bounded amount of approximation error. This result generalizes to several statistical models and types of input point sets.</p> / Dissertation

<p>Large scale geometric data is ubiquitous. In this dissertation, we design algorithms and data structures to process large scale geometric data efficiently. We design algorithms for some fundamental geometric optimization problems that arise in motion planning, machine learning and computer vision.</p><p>For a stream S of n points in d-dimensional space, we develop (single-pass) streaming algorithms for maintaining extent measures such as the minimum enclosing ball and diameter. Our streaming algorithms have a work space that is polynomial in d and sub-linear in n. For problems of computing diameter, width and minimum enclosing ball of S, we obtain lower bounds on the worst-case approximation ratio of any streaming algorithm that uses polynomial in d space. On the positive side, we design a summary called the blurred ball cover and use it for answering approximate farthest-point queries and maintaining approximate minimum enclosing ball and diameter of S. We describe a streaming algorithm for maintaining a blurred ball cover whose working space is linear in d and independent</p><p>of n.</p><p>For a set P of k pairwise-disjoint convex obstacles in 3-dimensions, we design algorithms and data structures for computing Euclidean shortest path between source s and destination t. The running time of our algorithm is linear in n and the size and query time of our data structure is independent of n. We follow a summary based approach, i.e., quickly compute a small sketch Q of P whose size is independent of n and then compute approximate shortest paths with respect to Q.</p><p>For d-dimensional point sets A and B, |A| |B| n, and for a parameter &epsilon > 0,</p><p>We give an algorithm to compute &epsilon-approximate minimum weight perfect matching of A and B under d(. , .) in time O(n<super>1.5</super>&tau(n)) ; here &tau(n) is the query/update time of a dynamic weighted nearest neighbor under d(. , .). When A, B are point sets from</p><p>a bounded integer grid, for L₁ and L_infinity-norms, our algorithm computes minimum weight</p><p>perfect matching of A and B in time O(n<super>1.5</super>). Our algorithm also extends to a generalization of matching called the transportation problem.</p><p>We also present an O(n polylog n ) time algorithm that computes under any L_p-</p><p>norm, an &epsilon-approximate minimum weight perfect matching of A and B with high probability; all previous algorithms take </p><p>O(n<super>1.5</super> time. We approximate the L_p norm using a distance function, based on a randomly shifted quad-tree. The algorithm iteratively generates an approximate minimum-cost augmenting path under the new distance function in</p><p>time proportional to the length of the path. We show that the total length of the augmenting paths generated by the algorithm is O(n log n) implying a near-linear running time.</p><p>All the problems mentioned above have a history of more than two decades and algorithms presented here improve previous work by an order of magnitude. Many of these improvements are obtained by new geometric techniques that might have broader applications</p><p>and are of independent interest.</p> / Dissertation

The problem of finding the convex hull of a set of points in the plane is one of the fundamental and well-studied problems in Computational Geometry. However, for a set of imprecise points, the convex hull problem has not been thoroughly investigated. By imprecise points, we refer to a region in the plane inside which one point may lie. We are particularly interested in finding a minimum perimeter convex hull of a set of imprecise points, where the imprecise points are modelled as line segments. Currently, the best known algorithm that solves the minimum perimeter convex hull problem has an exponential running time in the worst case. It is still unknown whether this problem is NP-hard. We explore several approximation algorithms for this problem. Finally we propose a constant factor approximation algorithm that runs in O(nlogn) time. / Thesis (Master, Computing) -- Queen's University, 2008-11-28 14:47:15.169

It is hard to imagine the modern world without wireless communication. Wireless networks are, however, challenging inasmuch as they are useful. Because of their complexity, wireless networks have introduced a myriad of new problems into the field of algorithms. To tackle the new computational challenges, specific models have been devised to suit wireless networks. Most remarkably, wireless networks can be modelled as geometric graphs. This allows us to address problems in wireless networks using tools from the fields of graph theory, graph algorithms, and computational geometry. Our results have applications to routing, coverage detection, data collection, and fault recovery, among other issues in this area. To be more specific, we investigate three major problems: a geometric approach to fault recovery; the distributed computation of Voronoi diagrams; and finding Hamiltonian cycles in hexagonal networks. Our geometric approach to fault recovery has been experimentally proved superior to an existing combinatorial approach. The distributed algorithm we propose for computing Voronoi diagrams of networks is the first non-trivial algorithm that has been proved to perform this task correctly; its efficiency has been demonstrated through simulations. Regarding the Hamiltonian cycle problem of hexagonal networks, we have advanced this topic by providing conditions for the existence of such a cycle, in addition to new insight on its complexity for the "solid" hexagonal grid case. Although we present satisfying solutions to several of the addressed problems, plenty is left to be done. In this regard, we identify a set of open problems that will be subject of research for years to come. / Thesis (Ph.D, Computing) -- Queen's University, 2009-11-25 21:04:37.0

A crease pattern is an embedded planar graph on a piece of paper. An m × n map is a rectangular piece of paper with a crease pattern that partitions the paper into an m × n regular grid of unit squares. If a map has a configuration such that all the faces of the map are stacked on a unit square and the paper does not self-intersect, then it is flat foldable, and the linear ordering of the faces is called a valid linear ordering. Otherwise, the map is unfoldable. In this thesis, we show that, given a linear ordering of the faces of an m × n map, we can decide in linear time whether it is a valid linear ordering or not. We also define a class of unfoldable 2 × n crease patterns for every n ≥ 5. / Graduate / 0984

Thesis (M.S.)--University of Nevada, Reno, 2008. / "August 2008." Includes bibliographical references (leaves 52-55). Online version available on the World Wide Web.

Orientadores: Pedro Jussieu de Rezende, Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-23T03:33:56Z (GMT). No. of bitstreams: 1 Silva_AndreCarvalho_M.pdf: 846347 bytes, checksum: ec1253f464900a70a0ef3bb68f9af1fa (MD5) Previous issue date: 2013 / Resumo: Grafos de visibilidade entre vértices de polígonos são estruturas que resumem as informações de visibilidade de tais vértices. Existem três relevantes problemas relativos a grafos de visibilidade: caracterização, reconhecimento e reconstrução. O problema da caracterização consiste em encontrar um conjunto de condições necessárias e suficientes para a classe de grafos de visibilidade. A procura de uma forma algorítmica para se reconhecer quando um grafo é de visibilidade define o problema de reconhecimento. O problema de reconstrução trata da questão de se reconstruir um polígono a partir de um grafo de visibilidade de tal forma que este seja isomorfo ao grafo de visibilidade do polígono. Neste trabalho, abordamos estes problemas para uma subclasse destes grafos: grafos de visibilidade de leques convexos. Dois resultados principais são apresentados nesse trabalho. O primeiro deles é um conjunto de três condições necessárias que um grafo de visibilidade de um leque convexo deve satisfazer. Adicionalmente, mostramos que estas condições são necessárias e suficientes para grafos de visibilidade de pseudo-leques convexos. Um resultado colateral deste processo é a equivalência entre grafos de visibilidade entre vértices, e grafos de visibilidade vértice-aresta, para leques convexos em posição geral. O segundo resultado consiste em que podemos reduzir o problema de reconstrução de polígonos unimonótonos para o mesmo problema para leques convexos / Abstract: The (vertex) visibility graph of a polygon is a graph that gathers all the visibility information among the vertices of the polygon. Three relevant problems related to visibility graphs are: characterization, recognition and reconstruction. Characterization calls for a set of necessary and sufficient conditions that every visibility graph must satisfy. Recognition deals with the problem of determining whether a given graph is the visibility graph of some polygon. Reconstruction asks for the generation of a polygon whose visibility graph is isomorphic to a given visibility graph. In this work, we study these problems on a restricted class of polygons, namely, convex fans: polygons that contain a convex vertex in its kernel. This work is comprised of two main results. The first one presents three necessary conditions that visibility graphs of convex fans must satisfy. We also show that those conditions are necessary and sufficient for visibility graphs of convex pseudo-fans. As a byproduct, we show that we can construct the vertex-edge visibility graph of a convex fan in general position from its vertex visibility graph. In the second major result, we show that we can reduce the reconstruction problem of unimonotone polygons to the same problem for convex fans / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T08:54:01Z (GMT). No. of bitstreams: 1 Selmi-Dei_FabioPakk_M.pdf: 2287860 bytes, checksum: 97e2fc68f82f1ee33b0e737ed3b9f831 (MD5) Previous issue date: 2005 / Resumo: Visualizadores são softwares capazes de gerar, através de recursos gráficos computacionais, figuras geométricas a partir de estruturas de dados e seus estados. Suas imagens facilitam a compreensão e depuração de algoritmos, bem como aumentam a intuição do usuário sobre os objetos geométricos e o espaço que os abriga. O presente trabalho descreve o projeto e a criação de um visualizador geométrico para uma extensão de CGAL ao plano projetivo orientado ('T POT 2'). CGAL é uma biblioteca de algoritmos geométricos e estruturas de dados desenvolvida por um consórcio de universidades com o objetivo de ser uma ferramenta de fácil acesso usada no desenvolvimento de aplicações que necessitem resolver problemas geométricos em 'R POT 2'. Através do trabalho [dO04], esta biblioteca foi estendida para incorporar 'T POT 2', preservando sua robustez, corretude e confiabilidade. O plano projetivo orientado é um espaço geométrico estritamente maior que o plano cartesiano 'R POT 2', porém com geometria semelhante. Uma das principais características de 'T POT 2' é o uso de coordenadas homogêneas sinaladas, o que permite lidar com o conceito de pontos no infinito de maneira homogênea ao tratamento dos pontos do plano, possibilitando o projeto de algoritmos geométricos que não mais precisam tratar separadamente muitos casos particulares, tornando-os mais simples e sucintos. Neste contexto, o visualizador aqui descrito tem por finalidade a criação de um ambiente de visualização que permite a observação das características intrínsecas à geometria projetiva orientada, o que é de grande benefício para o usuário-programador da extensão de CGAL para 'T POT 2' / Abstract: A graphical viewer is a software that enables the display of geometric figures from data structures and their varying states. The images it provides improve comprehension, make debugging easier and raise the users' intuition regarding geometric objects and their embedding space. The present work describes the design and creation of a geometrical viewer for an oriented projective plane ('T POT 2') extension of CGAL. CGAL is a library of geometric algorithms and data structures developed by a consortium of universities with the goal of producing an easy-to-use tool for building applications that require problem solving in 'R POT 2'. In [dO04], Oliveira describes an extension of this library that incorporates 'T POT 2' into CGAL, while adhering to its robustness, correctness and reliability. The oriented projective plane is a geometric space strictly larger than the Cartesian plane R2, though with similar geometry. One of the main features of 'T POT 2' is the use of signed homogeneous coordinates, which enables one to work with points at infinity in a way similar to working with proper points on the plane, allowing for the design of algorithms that no longer need to handle many particular cases, making them simpler and shorter. In this context, the viewer described here has the purpose of providing a visualization system that allows for the perception of the intrinsic characteristics of the oriented projective geometry, which is of great benefit to programmers of the extension of CGAL to 'T POT 2' / Mestrado / Geometria Computacional / Mestre em Ciência da Computação

Este trabalho aborda dois problemas de geometria computacional: união de círculos e união de (vários) polígonos. Para o problema da união de círculos, os principais algoritmos da literatura são revisados e um algoritmo simples, porém ineficiente, é introduzido. Este algoritmo é então adaptado para resolver o problema da união de polígonos, produzindo um algoritmo que é competitivo com o estado da arte e, dependendo da aplicação, utiliza menos armazenamento. / This work deals with two problems from the field of computational geometry: union of circles and union of (many) polygons. For the union of circles problem, the main algorithms in the literature are revised and a simple, albeit inefficient, algorithm is introduced. This algorithm is then adapted to solve the union of polygons problem, resulting in an algorithm that is competitive with the state of the art and, depending on the application, makes use of less storage.

<p>In the blooming era of smart edge devices, surveillance cameras have been deployed in many locations. Surveillance cameras are most useful when they are spaced out to maximize coverage of an area. However, deciding where to place cameras is an NP-hard problem and researchers have proposed heuristic solutions. Existing work does not consider a significant restriction of computer vision: in order to track a moving object, the object must occupy enough pixels. The number of pixels depends on many factors (How far away is the object? What is the camera resolution? What is the focal length?). In this study we propose a camera placement method that identifies effective camera placement in arbitrary spaces, and can account for different camera types as well. Our strategy represents spaces as polygons, then uses a greedy algorithm to partition the polygons and determine the cameras' locations to provide desired coverage. The solution also makes it possible to perform object tracking via overlapping camera placement. Our method is evaluated against complex shapes and real-world museum floor plans, achieving up to 85% coverage and 25% overlap.</p>