Browsing by Subject "Computational Geometry"
- Results Per Page
- Sort Options
Item Open Access Geometric Approximation Algorithms - A Summary Based Approach(2012) Raghvendra, SharathkumarLarge 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.
Item Open Access Geometric Hitting Sets and Their Variants(2011) Ganjugunte, Shashidhara KrishnamurthyThis thesis explores a few geometric optimization problems that arise
in robotics and sensor networks. In particular we present efficient
algorithms for the hitting-set problem and the budgeted hitting-set problem.
Given a set of objects and a collection of subsets of the objects,
called ranges, the hitting-set problem asks for a minimum number of
objects that intersect all the subsets in the collection.
In geometric settings, objects are
typically a set of points and ranges are defined by a set of geometric
regions (e.g., disks or polygons), i.e., the subset of points lying in each
region forms a range.
The first result of this thesis is an efficient algorithm for an instance
of the hitting-set problem in which both the set of points and the set
of ranges are implicitly defined. Namely, we are given a convex
polygonal robot and a set of convex polygonal obstacles, and we wish
to find a small number of congruent copies of the robot that intersect
all the obstacles.
Next, motivated by the application of sensor placement in sensor networks,
we study the so-called ``art-gallery'' problem. Given a polygonal
environment, we wish to place the minimum number of guards so that
the every point in the environment is visible from at least one guard.
This problem can be formulated as a hitting-set problem. We present
a sampling based algorithm for this problem and study various extensions
of this problem.
Next, we study the geometric hitting-set problem in a dynamic setting,
where the objects and/or the ranges change with time and the goal is
to maintain a hitting set. We present algorithms
which maintain a small size hitting set with sub-linear update time.
Finally, we consider the budgeted hitting-set problem, in which we
are asked to choose a bounded number of objects that intersect as many
ranges as possible. Motivated by applications in network vulnerability
analysis we study this problem in a probabilistic setting.
Item Open Access Small and Stable Descriptors of Distributions for Geometric Statistical Problems(2009) Phillips, Jeff M.This thesis explores how to sparsely represent distributions of points for geometric statistical problems. A coreset 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 ε. Two examples of coresets are ε-samples and ε-kernels. An ε-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 ε-kernel approximates the width of a point set in all directions. Both coresets have size that depends only on ε, 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.
We reduce the size of ε-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 ε-samples of probability distributions.
We show how to maintain “stable” ε-kernels, that is if the point set P changes by a small amount, then the ε-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 ε-kernels.
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 ε-kernels and ε-samples for these uncertain data sets.
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.