Tessellations for Geometric Optimization

Abstract

This thesis is concerned with the study of some tessellations (or subdivisions) of the plane or of the space and their relation to some optimization problems. Several of the results have a combinatorial flavor, whereas others are strongly connected to the geometry underlying the corresponding problems. The work combines theoretical statements with applied implications and related algorithms, making use of linear algebra, convex geometry, graph theory and many other tools from discrete and computational geometry. Regular subdivisions are tessellations resulting from the projection of the lower faces of a polyhedron. In the first part of this thesis, we generalize regular subdivisions introducing the class of recursively-regular subdivisions. Informally speaking, a recursively-regular subdivision is a subdivision that can be obtained by splitting some faces of a regular subdivision by other regular subdivisions (and continue recursively). We also define the finest regular coarsening and the regularity tree of a subdivision. We derive several properties of these two objects, which reflect certain structure in the class of non-regular subdivisions. In particular, the finest regular coarsening of a subdivision is the regular subdivision that is (in a sense) most similar to it. We show that the class of recursively-regular subdivisions is a proper superclass of the regular subdivisions and a proper subclass of the visibility-acyclic subdivisions (in the sense of an acyclicity theorem by Edelsbrunner). We also show that there exist point sets whose recursively-regular triangulations are not connected by geometric bistellar flips. We then derive several algorithms related to the studied objects, and point out applications of the main results. In particular, we present relations to tensegrity theory, data visualization, and graph embedding problems. Special attention is paid to the problem of covering the space by placing given floodlights at given points, for which we extend results known since 1981 and discuss two variants of the original problem. The second part is concerned with the study of optimal partial matchings for pairs of point sets under translations. First, we regard the least-squares cost function. The best approach to this problem so far is to construct (and explore) a particular tessellation of the space of translations. In every tile of the tessellation there is one matching that is optimal for any position of the point sets corresponding to a translation in that tile. We give the first non- trivial bound on the complexity of this tessellation in dimensions two and higher, and study several structural properties that lead to algorithms whose running time is polynomial in the size of the larger set. We address then the analogous problem under the bottleneck cost function. This cost function assigns to every matching the largest distance defined by a matched pair of points. An associated tessellation is shown to have polynomial complexity. This result, together with graph-theoretical tools, allows us to obtain efficient algorithms for the computation of the corresponding minimum under translations that are sensitive to the size of the smaller of the two sets. The lexicographic variant of the bottleneck cost is analyzed as well. Finally, we explore natural directions for the generalization of the problems of matching under translations to which many of our results extend.

In dieser Arbeit betrachten wir Parkettierungen (man sagt auch Unterteilungen) der Ebene und des Raumes sowie ihren Zusammenhang mit verschiedenen Optimierungsproblemen. Einige der Resultate sind kombinatorischer Natur, andere wiederum nutzen stark geometrische Eigenschaften der Probleme. Diese Dissertation kombiniert theoretische Ergebnisse mit konkreten Anwendungen und dazugehörigen Algorithmen mithilfe von Methoden der linearen Algebra, konvexen Geometrie, Graphentheorie und vielen weiteren Hilfsmitteln aus der diskreten und algorithmischen Geometrie. Reguläre Unterteilungen sind Parkettierungen, die durch die Projektion der Seiten eines Polyeders entstehen. Im ersten Teil verallgemeinern wir reguläre Unterteilungen zu rekursiv-regulären Unterteilungen: eine rekursiv-reguläre Unterteilung ist eine Unterteilung, die durch rekursives Aufsplitten von Flächen einer regulären Unterteilung in weitere reguläre Unterteilungen konstruiert werden kann. Darauf aufbauend führen wir die feinste reguläre Vereinfachung und den Regularitätsbaum einer Unterteilung ein. Wir leiten verschiedene Eigenschaften dieser Objekte her, die die zugrunde liegende Struktur der Klasse der nicht-regulären Unterteilungen widerspiegeln. Insbesondere ist die feinste reguläre Unterteilung einer Unterteilung die in gewissem Sinne «ähnlichste» reguläre Unterteilung. Wir zeigen, dass die Klasse der rekursiv-regulären Unterteilungen die Klasse der regulären Unterteilungen echt enthält und andererseits eine echte Teilklasse der azyklischen Sichtbarkeitsunterteilungen (im Sinne des Acyclicity Theorem von Edelsbrunner) ist. Wir beweisen außerdem die Existenz von Punktmengen, deren rekursiv-regulären Triangulierungen nicht durch geometrisch bistellare Flips ineinander überführt werden können. In Zusammenhang mit den theoretischen Ergebnissen entwickeln wir mehrere Algorithmen und stellen verschiedene Anwendungsmöglichkeiten der Hauptergebnisse vor. Insbesondere zeigen wir Verbindungen der betrachteten Objekte zu der Tensigritätstheorie, der Datenvisualisierung und Grapheinbettungsproblemen auf. Im Vordergrund steht dabei das Problem, einen d-dimensionalen Raum mit Flutlichtern auszuleuchten, die nur an bestimmten Punkten positioniert werden können. Wir verallgemeinern verschiedene, bereits seit 1981 bekannte Resultate und gehen im Detail auf zwei verschiedene Varianten des ursprünglichen Problems ein. Der zweite Teil der Dissertation beschäftigt sich mit optimalen partiellen Matchings von zwei gegebenen Punktmengen, wobei Parallelverschiebungen der ersten Punktmenge erlaubt sind. Zu Beginn betrachten wir das Problem mit der least-squares-Kostenfunktion. Der beste bekannte Ansatz für dieses Problem ist die Konstruktion einer geeigneten Parkettierung des Raumes der Parallelverschiebungen. In jeder Zelle der Parkettierung gibt es ein Matching, das für alle Positionen der Punktmengen, die durch die Parallelverschiebungen der Zelle bestimmt sind, optimal ist. Wir beweisen die erste nichttriviale Komplexitätsschranke für solche Parkettierungen in zwei und mehr Dimensionen und betrachten verschiedene strukturelle Eigenschaften, die benutzt werden können um Algorithmen zu entwickeln, deren Laufzeit polynomial in der Kardinalität der größeren Punktmenge ist. Darauf aufbauend betrachten wir das analoge Problem mit der bottleneck Kostenfunktion. Diese weist jedem Matching die größte Distanz der gematchten Punktpaare zu. Wir zeigen, dass eine zugehörige Parkettierung polynomielle Komplexität hat. Kombiniert mit verschiedenen Resultaten aus der Graphentheorie kann so ein effizienter Algorithmus hergeleitet werden, der, falls Parallelverschiebungen erlaubt sind, ein Matching mit minimalen Kosten berechnet und dessen Laufzeit sensitiv gegenüber der Größe der kleineren Punktmenge ist. Zuletzt wird auch die lexikographische Variante dieses Problems analysiert.