Computer Science Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2756
Browse
4 results
Search Results
Item Adaptive Sampling for Geometric Approximation(2020) Abdelrazek, Ahmed Abdelkader; Mount, David M; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Geometric approximation of multi-dimensional data sets is an essential algorithmic component for applications in machine learning, computer graphics, and scientific computing. This dissertation promotes an algorithmic sampling methodology for a number of fundamental approximation problems in computational geometry. For each problem, the proposed sampling technique is carefully adapted to the geometry of the input data and the functions to be approximated. In particular, we study proximity queries in spaces of constant dimension and mesh generation in 3D. We start with polytope membership queries, where query points are tested for inclusion in a convex polytope. Trading-off accuracy for efficiency, we tolerate one-sided errors for points within an epsilon-expansion of the polytope. We propose a sampling strategy for the placement of covering ellipsoids sensitive to the local shape of the polytope. The key insight is to realize the samples as Delone sets in the intrinsic Hilbert metric. Using this intrinsic formulation, we considerably simplify state-of-the-art techniques yielding an intuitive and optimal data structure. Next, we study nearest-neighbor queries which retrieve the most similar data point to a given query point. To accommodate more general measures of similarity, we consider non-Euclidean distances including convex distance functions and Bregman divergences. Again, we tolerate multiplicative errors retrieving any point no farther than (1+epsilon) times the distance to the nearest neighbor. We propose a sampling strategy sensitive to the local distribution of points and the gradient of the distance functions. Combined with a careful regularization of the distance minimizers, we obtain a generalized data structure that essentially matches state-of-the-art results specific to the Euclidean distance. Finally, we investigate the generation of Voronoi meshes, where a given domain is decomposed into Voronoi cells as desired for a number of important solvers in computational fluid dynamics. The challenge is to arrange the cells near the boundary to yield an accurate surface approximation without sacrificing quality. We propose a sampling algorithm for the placement of seeds to induce a boundary-conforming Voronoi mesh of the correct topology, with a careful treatment of sharp and non-manifold features. The proposed algorithm achieves significant quality improvements over state-of-the-art polyhedral meshing based on clipped Voronoi cells.Item Approximation Algorithms for Geometric Clustering and Touring Problems(2018) Bercea, Ioana Oriana; Khuller, Samir; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Clustering and touring are two fundamental topics in optimization that have been studied extensively and have ``launched a thousand ships''. In this thesis, we study variants of these problems for Euclidean instances, in which clusters often correspond to sensors that are required to cover, measure or localize targets and tours need to visit locations for the purpose of item delivery or data collection. In the first part of the thesis, we focus on the task of sensor placement for environments in which localization is a necessity and in which its quality depends on the relative angle between the target and the pair of sensors observing it. We formulate a new coverage constraint that bounds this angle and consider the problem of placing a small number of sensors that satisfy it in addition to classical ones such as proximity and line-of-sight visibility. We present a general framework that chooses a small number of sensors and approximates the coverage constraint to arbitrary precision. In the second part of the thesis, we consider the task of collecting data from a set of sensors by getting close to them. This corresponds to a well-known generalization of the Traveling Salesman Problem (TSP) called TSP with Neighborhoods, in which we want to compute a shortest tour that visits at least one point from each unit disk centered at a sensor. One approach is based on an observation that relates the optimal solution with the optimal TSP on the sensors. We show that the associated bound can be improved unless we are in certain exceptional circumstances for which we can get better algorithms. Finally, we discuss Maximum Scatter TSP, which asks for a tour that maximizes the length of the shortest edge. While the Euclidean version admits an efficient approximation scheme and the problem is known to be NP-hard in three dimensions or higher, the question of getting a polynomial time algorithm for two dimensions remains open. To this end, we develop a general technique for the case of points concentrated around the boundary of a circle that we believe can be extended to more general cases.Item APPROXIMATION ALGORITHMS FOR POINT PATTERN MATCHING AND SEARCHI NG(2010) Cho, Minkyoung; Mount, David M; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Point pattern matching is a fundamental problem in computational geometry. For given a reference set and pattern set, the problem is to find a geometric transformation applied to the pattern set that minimizes some given distance measure with respect to the reference set. This problem has been heavily researched under various distance measures and error models. Point set similarity searching is variation of this problem in which a large database of point sets is given, and the task is to preprocess this database into a data structure so that, given a query point set, it is possible to rapidly find the nearest point set among elements of the database. Here, the term nearest is understood in above sense of pattern matching, where the elements of the database may be transformed to match the given query set. The approach presented here is to compute a low distortion embedding of the pattern matching problem into an (ideally) low dimensional metric space and then apply any standard algorithm for nearest neighbor searching over this metric space. This main focus of this dissertation is on two problems in the area of point pattern matching and searching algorithms: (i) improving the accuracy of alignment-based point pattern matching and (ii) computing low-distortion embeddings of point sets into vector spaces. For the first problem, new methods are presented for matching point sets based on alignments of small subsets of points. It is shown that these methods lead to better approximation bounds for alignment-based planar point pattern matching algorithms under the Hausdorff distance. Furthermore, it is shown that these approximation bounds are nearly the best achievable by alignment-based methods. For the second problem, results are presented for two different distance measures. First, point pattern similarity search under translation for point sets in multidimensional integer space is considered, where the distance function is the symmetric difference. A randomized embedding into real space under the L1 metric is given. The algorithm achieves an expected distortion of O(log2 n). Second, an algorithm is given for embedding Rd under the Earth Mover's Distance (EMD) into multidimensional integer space under the symmetric difference distance. This embedding achieves a distortion of O(log D), where D is the diameter of the point set. Combining this with the above result implies that point pattern similarity search with translation under the EMD can be embedded in to real space in the L1 metric with an expected distortion of O(log2 n log D).Item Approximate Range Searching In The Absolute Error Model(2007-11-28) Fonseca, Guilherme Dias da; Mount, David M; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Range searching is a well known problem in computational geometry. We consider this problem in the context of approximation, where an approximation parameter eps > 0 is provided. Most prior work on this problem has focused on the relative error model, where each range shape R is bounded, and points within distance eps diam(R) of the range's boundary may or may not be included. We introduce a different approximation model, called the absolute error model, in which points within distance eps of the range's boundary may or may not be included, regardless of the diameter of the range. We consider sets of ranges consisting of general convex bodies, axis-aligned rectangles, halfspaces, Euclidean balls, and simplices. We examine a variety of problem formulations, including range searching under general commutative semigroups, idempotent semigroups, groups, range emptiness, and range reporting. We apply our data structures to several related problems, including range sketching, approximate nearest neighbor searching, exact idempotent range searching, approximate range searching in the data stream model, and approximate range searching in the relative model.