Guarding and Reconfiguration: Computational Complexity and Algorithm Design

Rieck, Christian

doi:10.24355/dbbs.084-202306221312-0

Published

Guarding and Reconfiguration : Computational Complexity and Algorithm Design

English
German

In this thesis, we deal with a variety of problems from computational geometry in the broad context of guarding and reconfiguration. Our path is guided by two fundamental questions:

How difficult is the problem at hand?
How can we tackle the problem algorithmically?

The answers to the first question show that all considered problems are difficult. More precisely, we show NP-hardness by reducing from several variants of the Boolean satisfiability problem. In view of the second question, we provide approximation algorithms, focus on special cases, or present algorithms that compute worst-case optimal solutions.

In the context of guarding, we study a variant of the art gallery problem in which guards should be far apart, for vertex guards in polyominoes. We show that a distance of 3 between guards is sometimes necessary and always sufficient. Furthermore, we show that the problem can be solved optimally in tree-shaped polyominoes. Additionally, we prove that it is NP-hard to decide whether a distance of 5 is realizable, even in thin polyominoes.

Afterwards, we turn our focus to problems that concern the parallel reconfiguration of robots or particles in different settings. In the first setting, the robots move by themselves, and independently of the others. In this scenario, we are given two connected configurations of robots on the integer grid and seek for a schedule to reconfigure the first into the second configuration while avoiding collisions between robots and keeping the whole arrangement connected at all times. Our goal is to minimize the makespan, that is the total time until the last robot arrives at its target. We show that it is NP-hard to decide whether a makespan of 2 exists. Complementary, we present algorithms that, under certain scaling conditions, achieve a makespan that is no worse than a constant times the maximum distance from a robot's start to its target position. We study the unlabeled and the labeled variant.

In the second setting, particles are moved by a global external force, that is, all particles move synchronously in the same direction. We distinguish the cases in which the particles either move as far as possible, or only one step at a time. We consider the constructibility of shapes, as well as gathering all particles at a single position. In both models, we show that constructibility of a three-dimensional shape is NP-hard. On the algorithmic side, we provide approximation algorithms for a natural optimization variant, and give polynomial time algorithms for special cases. We further show that in the single step model constantly scaled shapes are always constructible. Concerning the gathering problem in the single step model, we show NP-hardness for deciding whether ``short'' gathering sequences exist.
Furthermore, we give strategies that either gather a significant number of particles in a few steps, or merge two specific particles. In the full tilt model, we prove that it is NP-hard to decide whether placing a certain number of obstacles suffices to gather all particles at a predetermined position.

At the end of each chapter, we outline interesting questions for future work.

In dieser Arbeit befassen wir uns mit einer Vielzahl von Problemen der algorithmischen Geometrie im Kontext von Wächterproblemen und Rekonfigurationen. Unser Weg wird von zwei grundlegenden Fragen geleitet:

Wie schwer ist das betrachtete Problem?
Wie können wir das Problem algorithmisch angehen?

Die Antworten auf die erste Frage zeigen, dass alle betrachteten Probleme schwer sind. Genauer gesagt zeigen wir durch Reduktionen von Varianten des booleschen Erfüllbarkeitsproblems, dass die Probleme NP-schwer sind. Im Hinblick auf die zweite Frage liefern wir Approximationsalgorithmen, konzentrieren uns auf Spezialfälle, oder stellen Algorithmen vor, die worst case optimale Lösungen berechnen.

Im Zusammenhang von Wächterproblemen untersuchen wir eine Variante des Kunstgalerieproblems, bei der die Wächter weit voneinander entfernt sein sollen. Für Vertex-Wächter in Polyominos zeigen wir, dass ein Abstand von 3 zwischen den Wächtern manchmal notwendig und immer ausreichend ist. Des Weiteren präsentieren wir einen Algorithmus, der das Problem in baumförmigen Polyominos optimal löst. Sogar bei Einschränkung auf dünne Polyominos beweisen wir, dass es NP-schwer zu entscheiden ist, ob ein Abstand von 5 realisierbar ist.

Des Weiteren betrachten wir die parallele Rekonfiguration von Robotern oder Teilchen in verschiedenen Situationen. In der ersten Situation bewegen sich die Roboter selbstständig und unabhängig von den anderen. In diesem Szenario wollen wir zwei jeweils zusammenhängende Konfigurationen von Robotern ineinander transformieren. Dazu suchen wir nach einem Bewegungsplan für die Rekonfiguration der ersten in die zweite Konfiguration, wobei Kollisionen zwischen Robotern vermieden werden und die gesamte Anordnung zu jeder Zeit zusammenhängend bleibt. Unser Ziel ist es, die Zeitspanne zu minimieren, dass heißt die Gesamtzeit bis der letzte Roboter an seinem Ziel ankommt. Wir zeigen, dass es NP-schwer zu entscheiden ist, ob ein Bewegungsplan mit Zeitspanne von 2 existiert. Ergänzend dazu stellen wir Approximationsalgorithmen vor.

Bei der zweiten Variante werden die Teilchen durch eine globale externe Kraft bewegt, das heißt alle Teilchen bewegen sich synchron in dieselbe Richtung.
Wir unterscheiden ob sich die Teilchen so weit wie möglich oder nur einen Schritt bewegen. In beiden Modellen zeigen wir, dass die Konstruierbarkeit einer dreidimensionalen Form NP-schwer ist. Wir liefern Approximationsalgorithmen und geben Polynomialzeitalgorithmen für Spezialfälle an. Für das Einschrittmodell zeigen wir, dass konstant skalierte Formen immer konstruierbar sind und NP-schwere für die Entscheidung ob kurze Sequenzen existieren, die alle Teilchen an einer einzigen Position sammeln. Des Weiteren präsentieren wir Strategien, um eine signifikante Anzahl von Teilchen in wenigen Schritten zu sammeln oder zwei bestimmte Teilchen zusammenführen. Wir beweisen, dass es NP-schwer ist im Full-Tilt-Modell zu entscheiden, ob die Platzierung einer bestimmten Anzahl von Hindernissen ausreicht, um alle Partikel an einer vorgegebenen Position zu sammeln.

Am Ende jeden Kapitels zeigen wir offene Fragen für zukünftige Projekte auf.