Understanding, Modeling and Exploiting Structured Inputs for Geometric Problems
Final Report Abstract
Der traditionelle Ansatz beim Entwurf und der Analyse von Algorithmen beruht auf der worst-case Sichtweise. Dabei ist das Ziel, Algorithmen so zu entwerfen, dass sie das bestmögliche Verhalten für die schlimmstmögliche Eingabe zeitigen. Es wird nicht versucht, den Algorithmus für die jeweilige Anwendung zu optimieren. Dieser worst-case Ansatz hat sich als sehr erfolgreich erwiesen. Er erlaubt es, sich zunächst auf das Wesentliche zu konzentrieren und die Struktur der zugrundeliegenden Probleme zu erfassen, ohne dass zusätzliche Annahmen über das Anwendungsszenario zu Ablenkungen führen. Gleichzeitig hat es schon immer Ansätze gegeben, dieses Modell zu verfeinern, um bessere Ergebnisse zu erzielen. Gerade in letzter Zeit hat diese Richtung an Interesse gewonnen. Zum einen werden die zu verarbeitenden Datenmengen zu groß und komplex für worstcase Algorithmen. Zum anderen haben die Eingaben oft mehr Struktur, und wir wissen oft mehr über die Daten, als von den bisherigen Verfahren ausgenutzt wird. Das Ziel des Projektes war es, genauer zu beleuchten, wie sich verschiedene Strukturen der Eingabedaten charakterisieren lassen, und zu verstehen, welche Eigenschaften daraus folgen. Die Hoffnung war, effizientere und auch einfachere Algorithmen zu finden, die sich diese Struktur zunutze machen. Dabei haben wir uns auf Probleme aus der algorithmischen Geometrie konzentriert, da Eingang aus der Geometrie oft zusätzliche Eigenschaften besitzen, als es bei rein kombinatorischen Problemen der Fall ist. Im Laufe des Projekts ist es uns gelungen, diesem Ziel ein wenig näher zu kommen. So haben wir uns beispielsweise mit einer Klasse von geometrisch definierten Graphen beschäftigt, bei der die Knoten und Kanten geometrischen Objekten in der Ebene und den Beziehungen zwischen diesen Objekten entsprechen. Es hat sich herausgestellt, dass diese Graphen eine reichhaltige Struktur besitzen, die es uns erlaubt, algorithmische Aufgaben wie Breitensuche, die dynamische Aufrechterhaltung eines aufspannenden Baumes oder die verteilte Wegfindung effizienter zu lösen als mit herkömmlichen Methoden. Diese Untersuchungen haben uns auch auf einige interessante Nebenschauplätze geführt, wie zum Beispiel der Fragestellung, welcher Aufwand nötig ist, um eine attraktorbasierte Wegfindung in dreidimensionalen Polytopen zu ermöglichen. Wir konnten auch eine neue dynamische Datentruktur für Nächste-Nachbar-Suche in der Ebene bezüglich allgemeiner Metriken finden, welche sich bereits in anderen Zusammenhängen als nützlich erwiesen hat. Ein unerwarteter Nebeneffekt unseres Projekts war, dass wir neue Erkenntnisse zur algorithmischen Komplexität des klassischen Fréchet Abstandes erzielen konnten. Dies ergab sich aus der Feststellung, dass einige der Sichtweisen, die wir im Rahmen des Projektes entwickelt haben, sich für dieses Problem als nützlich erweisen. Dadurch konnten nach fast 20 Jahren den ersten verbesserten Algorithmus für das Problem finden und zu einem neuen Ansatz beitragen, der erklären soll, worin die algorithmische Schwierigkeit des Problems besteht.
Publications
- (2020) Routing in polygonal domains. Computational Geometry 87 101593
Banyassady, Bahareh; Chiu, Man-Kwun; Korman, Matias; Mulzer, Wolfgang; van Renssen, André; Roeloffzen, Marcel; Seiferth, Paul; Stein, Yannik; Vogtenhuber, Birgit; Willert, Max
(See online at https://doi.org/10.1016/j.comgeo.2019.101593) - Approximability of the discrete Fréchet distance. Journal of Computational Geometry (JoCG), 7(2):46–76, 2016
Karl Bringmann and Wolfgang Mulzer
(See online at https://doi.org/10.4230/LIPIcs.SOCG.2015.739) - Computing the Fréchet distance with a retractable leash. Discrete Comput. Geom., 56(2):315–336, 2016
Kevin Buchin, Maike Buchin, Rolf van Leusden, Wouter Meulemans, and Wolfgang Mulzer
(See online at https://doi.org/10.1007/s00454-016-9800-8) - Delta-fast tries: Local searches in bounded universes with linear space. In Proc. 15th Int. Symp. Alg. and Data Struct. (WADS), pages 361–372, 2017
Marcel Ehrhardt and Wolfgang Mulzer
(See online at https://doi.org/10.1007/978-3-319-62127-2_31) - Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. In Proc. 28th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 2495–2504, 2017
Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir
(See online at https://doi.org/10.1137/1.9781611974782.165) - Four Soviets walk the dog: Improved bounds for computing the Fréchet distance. Discrete Comput. Geom., 58(1):180–216, 2017
Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer
(See online at https://doi.org/10.1007/s00454-017-9878-7) - Combinatorics of beacon-based routing in three dimensions. In Proc. 13th Latin American Symp. Theoret. Inf. (LATIN), pages 346–360, 2018
Jonas Cleve and Wolfgang Mulzer
(See online at https://doi.org/10.1007/978-3-319-77404-6_26) - Recognizing generalized transmission graphs of line segments and circular sectors. In Proc. 13th Latin American Symp. Theoret. Inf. (LATIN), pages 683–696, 2018
Katharina Klost and Wolfgang Mulzer
(See online at https://doi.org/10.1007/978-3-319-77404-6_50) - Routing in unit disk graphs. Algorithmica, 80(3):830–848, 2018
Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth
(See online at https://doi.org/10.1007/s00453-017-0308-2) - Spanners for directed transmission graphs. SIAM J. Comput., 47(4):1585–1609, 2018
Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth
(See online at https://doi.org/10.1137/16M1059692)
