Geometric Hitting Sets and Their Variants

dc.contributor.advisor

Agarwal, Pankaj Kumar

dc.contributor.author

Ganjugunte, Shashidhara Krishnamurthy

dc.date.accessioned

2012-01-10T15:58:04Z

dc.date.available

2012-07-08T04:30:08Z

dc.date.issued

2011

dc.department

Computer Science

dc.description.abstract

This 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.

dc.identifier.uri

https://hdl.handle.net/10161/4972

dc.subject

Computer science

dc.subject

Computational Geometry

dc.subject

Hitting Set

dc.subject

Network vulnerability

dc.subject

Robotics

dc.subject

Sensor networks

dc.title

Geometric Hitting Sets and Their Variants

dc.type

Dissertation

duke.embargo.months

6

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Ganjugunte_duke_0066D_11124.pdf
Size:
2.64 MB
Format:
Adobe Portable Document Format

Collections