Exakte Berechnung des Voronoi-Diagramms für Polyeder im dreidimensionalen Raum

• Antragsteller: Dr. Michael Hemmer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2013
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 190739945

Viele Algorithmen aus dem Gebiet der Computational Geometry, wie sie zum Beispiel in Computer-Aided-Design Systemen verwendet werden, sind nicht robust. Durch unvermeidbare Rundungsfehler ist es zum Beispiel oft nicht möglich zu entscheiden, ob sich zwei Objekte nur sehr nahe kommen oder sich tatsächlich berühren. Dies kann dazu führen, dass falsche bzw. inkonsistente Entscheidungen innerhalb der Algorithmen getroffen werden. Zwar wurden auf dem Gebiet der Computeralgebra bereits sehr allgemeine Lösungsverfahren entwickelt, diese sind aber für den unmittelbaren Einsatz in der Praxis oft deutlich zu langsam. Unser grundsätzliches Forschungsinteresse ist es daher die besten Methoden aus den Gebieten der Computational Geometry, Solid Modeling und Computeralgebra so zu verknüpfen und weiterzuentwickeln, dass dies die Entwicklung effizienter, vollständiger und exakter geometrischer Algorithmen ermöglicht. In unserem Forschungsvorhaben wollen wir unsere Aufmerksamkeit auf das Voronoi-Diagramm, eine grundlegende Datenstruktur der Computational Geometry, richten. Das Voronoi-Diagramm repräsentiert bzgl. einer Menge von Eingabeobjekten die Zerlegung des Raumes in (Voronoi-)Zellen, so dass jede Zelle genau die Punkte enthält, die einem bestimmten Eingabeobjekt am nächsten sind. Unser Ziel ist die Entwicklung und Umsetzung eines effizienten, vollständigen und exakten Algorithmus, der das Voronoi-Diagramm für Polyeder im dreidimensionalen Raum berechnet. Nach unserer Kenntnis wäre dies der erste exakte, vollständige, und somit robuste, Algorithmus dieser Art. Wir erwarten dass ein erfolgreicher Abschluss unseres Projektes weitreichende Auswirkungen auf zukünftige Implementierungen komplexer dreidimensionaler geometrischer Strukturen im Allgemeinen hat, einem Bereich, der den Erfolgen im Zweidimensionalen noch deutlich nachsteht.

• DFG-Verfahren: Forschungsstipendien
• Internationaler Bezug: Israel
• Gastgeber: Professor Dr. Dan Halperin