Please use this identifier to cite or link to this item: doi:10.22028/D291-25690
Title: Algorithmic geometry via graphics hardware
Author(s): Denny, Markus Oswald
Language: English
Year of Publication: 2003
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
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.
Link to this record: urn:nbn:de:bsz:291-scidok-1756
hdl:20.500.11880/25746
http://dx.doi.org/10.22028/D291-25690
Advisor: Raimund Seidel
Date of oral examination: 14-Mar-2003
Date of registration: 19-Feb-2004
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
MarkusOswaldDenny_ProfDrRaimundSeidel.pdf8,02 MBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.