Geometric Approximation Algorithms - A Summary Based Approach

Abstract

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.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 independentof n.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.For d-dimensional point sets A and B, |A| |B| n, and for a parameter &epsilon > 0,We give an algorithm to compute &epsilon-approximate minimum weight perfect matching of A and B under d(. , .) in time O(n1.5&tau(n)) ; here &tau(n) is the query/update time of a dynamic weighted nearest neighbor under d(. , .). When A, B are point sets froma bounded integer grid, for L1 and Linfinity-norms, our algorithm computes minimum weightperfect matching of A and B in time O(n1.5). Our algorithm also extends to a generalization of matching called the transportation problem.We also present an O(n polylog n ) time algorithm that computes under any Lp-norm, an &epsilon-approximate minimum weight perfect matching of A and B with high probability; all previous algorithms take O(n1.5 time. We approximate the Lp 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 intime 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.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 applicationsand are of independent interest.