Geometric Approximation Algorithms - A Summary Based Approach

Loading...
Thumbnail Image

Date

2012

Authors

Raghvendra, Sharathkumar

Journal Title

Journal ISSN

Volume Title

Repository Usage Stats

549
views
519
downloads

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 independent

of 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 from

a bounded integer grid, for L1 and Linfinity-norms, our algorithm computes minimum weight

perfect 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 in

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.

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

and are of independent interest.

Description

Provenance

Citation

Citation

Raghvendra, Sharathkumar (2012). Geometric Approximation Algorithms - A Summary Based Approach. Dissertation, Duke University. Retrieved from https://hdl.handle.net/10161/5847.

Collections


Dukes student scholarship is made available to the public using a Creative Commons Attribution / Non-commercial / No derivative (CC-BY-NC-ND) license.