Algorithmic geometry via graphics hardware

Abstract

We develop a pixel-based model of computation relying on the power of modern graphics hardware. It provides the foundation on which we exemplarily discuss various problems arising in the field of algorithmic geometry. Our prime example is the computation of the Voronoi diagram of a planar point set via the lower envelope of an arrangement of cones. We give a detailed analysis of the error occurring due to the nature of pixel based algorithms. Furthermore, we present a method to achieve a significant speedup for the computation.

Wir entwickeln ein pixelbasiertes Berechnungsmodell, dem die Möglichkeiten moderner Grafikhardware zu Grunde liegt. Auf der Basis dieses Modells untersuchen wir exemplarisch verschiedene Probleme aus dem Gebiet der algorithmischen Geometrie. Unser Hauptbeispiel ist die Berechnung des Voronoi-Diagrammes einer planaren Produktmenge mittels der unteren Einhüllenden eines Arrangements von Kegeln. Wir führen eine detaillierte Analyse des Fehlers durch, der durch die Verwendung von pixelbasierten Algorithmen auftreten kann. Wir stellen dann eine Methode vor, um die Berechnung des Voronoi-Diagrammes erheblich zu beschleunigen.