Geometric Algorithms with Limited Work-Space

• Applicant: Professor Dr. Wolfgang Mulzer
• Subject Area: Theoretical Computer Science
• Term: from 2013 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 242753045

• Final Report Year: 2020

Final Report Abstract

In den letzten Jahren können wir in der Informatik zwei entgegengesetzte Trends beobachten: Auf der einen Seite werden die zur Verfügung stehenden Hardware-Ressourcen immer umfangreicher. Dies führt oft zu aufgeblasener Software, welche ohne Rücksicht auf Ressourcen und Effizienz entwickelt wird. Auf der anderen Seite sehen wir aber auch eine weite Verbreitung von kleinen Geräten, die nur über geringe Mengen an Speicher und Akkuvolumen verfügen. Software, die nicht in Hinblick auf den verfügbaren Speicherplatz entwickelt wurde, ist für ein solches Umfeld nicht geeignet. Und selbst wenn diese kleinen Geräte über größere Speicherkapazitäten verfügen sollten, kann es dennoch von Vorteil sein, die Anzahl der Schreiboperationen in der Software zu beschränken. Angesichts dieser Lage ist es sinnvoll, sich auf Algorithmen zu konzentrieren, die nur eine geringe Menge von Arbeitsspeicher mit Lese- und Schreibzugriff benötigen, während die Eingabe in einem Speicherbereich liegt, der nur gelesen werden kann. Das Ziel des vorliegenden Projektes ist es, Algorithmen für geometrische Probleme zu untersuchen, für die nur wenig Arbeitsspeicher benötigt wird. Das zugrundeliegende Modell ähnelt der üblichen reellen Registermaschine. Diese erlaubt es, wahlfrei auf die einzelnen Speicherzellen zuzugreifen, wobei jede Speicherzelle ein einzelnes Datenwort enthält. In unserem Modell unterscheiden wir aber zwischen zwei verschiedenen Arten von Speicherzellen: (i) Eingabezellen, auf welche nur lesend zugegriffen werden darf; und (ii) Arbeitszellen, die sowohl gelesen aus auch beschrieben werden können. Die Ausgabe muss sequentiell bereitgestellt werden und darf im Anschluss weder gelesen noch verändert werden. Die Speichereffizienz eines Algorithmus wird gemessen durch die Anzahl der Arbeitszellen, die der Algorithmus benötigt. Dabei gibt es zwei Extreme: Algorithmen, die nur eine konstante Anzahl von Arbeitszellen benötigen, und solche, bei denen die Anzahl der Arbeitszellen proportional mit der Eingabegröße wächst. Dazwischen besteht ein ganzes Spektrum von Möglichkeiten, welche wir als Zeit-Platz-Trade-Off bezeichnen. Im Rahmen des Projektes haben wir für zahlreiche klassische Probleme der algorithmischen Geometrie Methoden entwickelt, die einen Trade-Off zwischen Zeit und Platzbedarf ermöglichen. Insbesondere haben wir uns mit k-Sichtbarkeitsregionen in einfachen Polygonen, mit Voronoi Diagrammen und mit kürzesten aufspannenden Bäumen in der euklidischen Metrik beschäftigt. Für jedes dieser Probleme haben wir Methoden entwickelt, welche zwischen den besten bekannten Algorithmen für das Szenario von konstantem Arbeitsspeicher und für das Szenario von linearem Arbeitsspeicher interpolieren. Um diese Ergebnisse zu erhalten, haben wir tief in die Trickkiste der algorithmischen Geometrie gegriffen und einige bekannte Techniken an die neue Umgebung angepasst. Wir mussten aber auch neue Methoden entwickeln, die es so vorher noch nicht gegeben hat. Ein weiterer Aspekt des Projekts bestand in der experimentellen Evaluation unserer neuen Algorithmen. Wir haben einige unserer Algorithmen implementiert und in der Praxis getestet. Dabei stellte sich heraus, dass der beschränkte Speicherplatz zwar Einbußen in der Laufzeit mit sich bringt, die neuen Methoden aber durchaus für den praktischen Einsatz geeignet sind.

Publications

• Computational geometry column 67. SIGACT News, 49(2):77–94, 2018
  Bahareh Banyassady, Matias Korman, and Wolfgang Mulzer
  
• Improved timespace trade-offs for computing Voronoi diagrams. Journal of Computational Geometry (JoCG), 9(1):191–212, 2018
  Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein
  
• Time-space trade-offs for triangulations and Voronoi diagrams. Comput. Geom., 73:35–45, 2018
  Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein
  
• Time-space tradeoffs for computing Euclidean minimum spanning trees. In Proc. 13th Latin American Symp. Theoret. Inf. (LATIN), pages 108–119, 2018
  Bahareh Banyassady, Luis Barba, and Wolfgang Mulzer
  
• A time-space trade-off for computing the kvisibility region of a point in a polygon. Theoret. Comput. Sci., 789:13–21, 2019
  Yeganeh Bahoo, Bahareh Banyassady, Prosenjit K. Bose, Stephane Durocher, and Wolfgang Mulzer
  
• An experimental study of algorithms for geodesic shortest paths in the constant-workspace model. In Special Event on Analysis of Experimental Algorithms (SEA2 ), pages 317–331, 2019
  Jonas Cleve and Wolfgang Mulzer
  
• Dynamic disk connectivity. In Proc. 35 European Workshop Comput. Geom. (EWCG), pages 50:1–6, 2019
  Alexander Kauer and Wolfgang Mulzer
  
• Routing in polygonal domains. Comput. Geom., 87:101593, 2020.
  Bahareh Banyassady, Man-Kwun Chiu, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber, and Max Willert