Stabbing and Covering Geometric Objects in the Plane

Abstract

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 Fréchet 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.

Wir beschäftigen uns in dieser Arbeit mit verschiedenen geometrischen Überdeckungs- sowie Transversalenproblemen in der Ebene. Beide Gebiete zeigen ihre Relevanz durch zahlreiche Untersuchungen in der algorithmischen Geometrie. Die Fragestellungen sind häufig verwandt, da viele Überdeckungsprobleme dual zu Transversalenproblemen sind. Die Arbeit beginnt mit der Betrachtung von Transversalenproblemen. Zuerst beschäftigen wir uns mit einer Frage, die bereits 1987 von Tamir gestellt wurde: „Sei eine Menge von geometrischen Objekten in der Ebene gegeben. Kann man in polynomieller Zeit entscheiden, ob ein konvexes Polygon existiert, dessen Rand all diese Objekte aufspießt?“ Den Rand eines solchen Polygons nennen wir konvexe Transversale. Wir zeigen, dass es für viele geometrische Objekte NP-schwer ist zu entscheiden, ob eine konvexe Transversale existiert. Zusätzlich betrachten wir eine Optimierungsvariante für das Problem und zeigen, dass dieses Problem für die meisten betrachteten Objekte APX-schwer ist. Eine ähnliche Fragestellung ist zu entscheiden, ob ein gegebenes Polygon so gedreht, verschoben und gestreckt werden kann, dass seine Ecken eine gegebene Menge von geometrischen Objekten aufspießen. Dieses Problem wurde, soweit uns bekannt ist, bisher noch nicht betrachtet und wir präsentieren den ersten Polynomialzeitalgorithmus. Als Erweiterung dieser Problematik beschäftigen wir uns mit dem Problem Folgen von geometrischen Objekten mit Punktfolgen aufzuspießen. Dazu nehmen wir an, dass zwei Folgen von geometrischen Objekten gegeben sind. Hierzu werden zwei Punktfolgen gesucht, die die gegebenen Folgen aufspießen und deren Abstand minimal ist (wobei wir als Abstandsmaß die diskrete Fréchetdistanz wählen). Wir untersuchen dieses Problem unter der Bedingung, dass die Objekte Strecken oder Kreisscheiben sind. Im zweiten Teil der Arbeit betrachten wir Überdeckungsprobleme. Insbesondere untersuchen wir neue Versionen des 2-Zentren Problems, bei denen die Eingabe aus einer Menge D von Kreisscheiben besteht. Bei der ersten Variante sollen zwei kleinste, kongruente Kreisscheiben berechnet werden, die jede Kreisscheibe in D schneiden. Bei der zweiten Variante sollen alle Kreisscheiben in D von zwei kleinsten, kongruenten Kreisscheiben überdeckt werden. Zusätzlich untersuchen wir eine Optimierungsvariante des Problems und geben effiziente exakte Algorithmen und Approximationsalgorithmen an. Zum Schluss untersuchen wir das Problem, ein Rechteck mit größtem Flächeninhalt zu finden, das in ein konvexes Polygon einbeschrieben ist. Unter der Annahme, dass die Reihenfolge der Ecken des Polygons gegeben ist, präsentieren wir Approximationsalgorithmen mit logarithmischer Laufzeit.