Theses

In this thesis, we consider a variety of different geometric covering

and stabbing problems in the plane.

Stabbing and covering geometric objects are two widely studied problems

in computational geometry.

These problems are closely related; there are many cases where covering

problems are dual to stabbing problems.

We first study a problem that was posed by Tamir in 1987: "Given a set

of geometric objects in the plane, can one decide in

polynomial time whether there exists a convex polygon whose boundary

stabs every object ?" This boundary is then called a convex stabber. We

give an answer to this question by proving that deciding the existence

of a convex stabber is NP-hard for many types of geometric objects.

Additionally, we consider an optimization version and prove it to be

APX-hard for most of the considered objects.

A similar problem is deciding whether geometric objects can be stabbed

with the vertices of a rotated, scaled and translated copy of a given

polygon. To the best of our knowledge, this problem was not studied so

far and we present the first polynomial-time algorithm.

Another stabbing problem studied in this thesis, is the problem of

stabbing sequences of geometric objects: Given a distance measure and

two sequences of geometric objects, compute two point sequences that

stab them under the condition that the distance between these point

sequences is as small as possible (using the given distance measure). We

state efficient algorithms for this problem where the objects are either

line segments or disks and the distance measure is the discrete Frechet

distance.

Then, we consider covering problems. We study a new version of the

two-center problem where the input is a set

D of disks in the plane. We first

study the problem of finding two

smallest congruent disks such that each disk in D

intersects one of these two disks. Then, we study the problem of

covering the set D by two smallest congruent disks. We also

investigate an optimization version.

For these problems, we give efficient exact and approximation algorithms.

Finally, we investigate the problem of computing a largest area

rectangle inscribed in a convex polygon on n vertices. If the order of

the vertices of the polygon is given, we state approximation algorithms

whose running times are only logarithmically dependent on n.