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.
","abstract_html":"<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>","abstract_has_math":false,"creators":["Ganjugunte, Shashidhara Krishnamurthy"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Agarwal, Pankaj K"],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011","date_published":"2011","updated_at":"2026-07-24T02:07:19Z","subjects":["Computer science","Computational Geometry","Hitting Set","Network vulnerability","Robotics","Sensor networks"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/10161/4972","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Agarwal, Pankaj K"]},{"key":"dc:creator","label":"Author","values":["Ganjugunte, Shashidhara Krishnamurthy"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2012-01-10T15:58:04Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2012-07-08T04:30:08Z"]},{"key":"dc:date.issued","label":"Date","values":["2011"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer science","Computational Geometry","Hitting Set","Network vulnerability","Robotics","Sensor networks"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/10161/4972"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["Geometric Hitting Sets and Their Variants"]}]}],"canonical_facts":{"dc:contributor.advisor":["Agarwal, Pankaj K"],"dc:creator":["Ganjugunte, Shashidhara Krishnamurthy"],"dc:date.accessioned":["2012-01-10T15:58:04Z"],"dc:date.available":["2012-07-08T04:30:08Z"],"dc:date.issued":["2011"],"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","Computational Geometry","Hitting Set","Network vulnerability","Robotics","Sensor networks"],"dc:title":["Geometric Hitting Sets and Their Variants"],"dc:type":["Dissertation"]},"updated_at":"2026-07-24T02:07:19Z"}