UC Santa Barbara

In a geometric optimization problem, the goal is to optimize an objective function

subject to a set of constraints induced by a family of geometric objects. When these

constraints render the problem infeasible or cause the objective function value to be unacceptable,

a natural course of action is to remove or relax some of the constraints,

without changing the problem formulation too much. In this dissertation, we study some natural

formulations of two geometric optimization problems

subject to a fixed budget on the number of constraints that can be removed.

For most parts, our focus is on path finding problems in the plane in presence of polygonal obstacles,

where we are allowed to remove a small number of the obstacles. We first consider the case when

obstacles are overlapping such that no "feasible" path between a given source s and destination t exists.

Here, one would like to remove the minimum number of obstacles so that there exists an obstacle-free s--t path.

This problem is more commonly known as minimum constraint removal (MCR), and is known to be NP-hard,

even when obstacles are axis-aligned rectangles. We design approximation algorithms for MCR, which are based

on solving the related problem of computing a minimum color path in a colored graph.

Next, we consider the case when obstacles are disjoint (so a feasible path always exists) but even the shortest such

path is unacceptably long. For this case, we design polynomial-time algorithms to compute a set of at most k obstacles

removing which reduces the original shortest path by maximum amount. An important requirement is that the obstacles must be

convex polygons.

Finally, we consider another geometric optimization problem called maximum exposure.

Here, we are given a set of points P and a set of ranges R covering them,

and we would like to remove a subset of R with at most k ranges so as to `expose' (or uncover)

a maximum number of points. Our work here deals with designing approximation algorithms.