Show simple item record

dc.contributor.advisor Agarwal, Pankaj K en_US
dc.contributor.author Ganjugunte, Shashidhara Krishnamurthy en_US
dc.date.accessioned 2012-01-10T15:58:04Z
dc.date.available 2012-07-08T04:30:08Z
dc.date.issued 2011 en_US
dc.identifier.uri http://hdl.handle.net/10161/4972
dc.description Dissertation en_US
dc.description.abstract <p>This thesis explores a few geometric optimization problems that arise</p><p>in robotics and sensor networks. In particular we present efficient</p><p>algorithms for the hitting-set problem and the budgeted hitting-set problem.</p><p>Given a set of objects and a collection of subsets of the objects,</p><p>called ranges, the hitting-set problem asks for a minimum number of </p><p>objects that intersect all the subsets in the collection.</p><p>In geometric settings, objects are </p><p>typically a set of points and ranges are defined by a set of geometric</p><p>regions (e.g., disks or polygons), i.e., the subset of points lying in each </p><p>region forms a range.</p><p>The first result of this thesis is an efficient algorithm for an instance</p><p>of the hitting-set problem in which both the set of points and the set</p><p>of ranges are implicitly defined. Namely, we are given a convex</p><p>polygonal robot and a set of convex polygonal obstacles, and we wish</p><p>to find a small number of congruent copies of the robot that intersect</p><p>all the obstacles.</p><p>Next, motivated by the application of sensor placement in sensor networks,</p><p>we study the so-called ``art-gallery'' problem. Given a polygonal</p><p>environment, we wish to place the minimum number of guards so that</p><p>the every point in the environment is visible from at least one guard.</p><p>This problem can be formulated as a hitting-set problem. We present</p><p>a sampling based algorithm for this problem and study various extensions</p><p>of this problem.</p><p>Next, we study the geometric hitting-set problem in a dynamic setting,</p><p>where the objects and/or the ranges change with time and the goal is</p><p>to maintain a hitting set. We present algorithms </p><p>which maintain a small size hitting set with sub-linear update time.</p><p>Finally, we consider the budgeted hitting-set problem, in which we</p><p>are asked to choose a bounded number of objects that intersect as many</p><p>ranges as possible. Motivated by applications in network vulnerability</p><p>analysis we study this problem in a probabilistic setting.</p> en_US
dc.subject Computer science en_US
dc.subject Computational Geometry en_US
dc.subject Hitting Set en_US
dc.subject Network vulnerability en_US
dc.subject Robotics en_US
dc.subject Sensor networks en_US
dc.title Geometric Hitting Sets and Their Variants en_US
dc.type Dissertation en_US
dc.department Computer Science en_US
duke.embargo.months 6 en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record