KIT | KIT-Bibliothek | Impressum | Datenschutz

Algorithms for Triangles, Cones & Peaks

Funke, Daniel 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract (englisch):

Three different geometric objects are at the center of this dissertation: triangles, cones and peaks.
In computational geometry, triangles are the most basic shape for planar subdivisions.
Particularly, Delaunay triangulations are a widely used for manifold applications in engineering, geographic information systems, telecommunication networks, etc.
We present two novel parallel algorithms to construct the Delaunay triangulation of a given point set.
Yao graphs are geometric spanners that connect each point of a given set to its nearest neighbor in each of $k$ cones drawn around it.
They are used to aid the construction of Euclidean minimum spanning trees
or in wireless networks for topology control and routing.
We present the first implementation of an optimal $\mathcal{O}(n \log n)$-time sweepline algorithm to construct Yao graphs.
One metric to quantify the importance of a mountain peak is its isolation.
Isolation measures the distance between a peak and the closest point of higher elevation.
Computing this metric from high-resolution digital elevation models (DEMs) requires efficient algorithms.
We present a novel sweep-plane algorithm that can calculate the isolation of all peaks on Earth in mere minutes.


Volltext §
DOI: 10.5445/IR/1000165647
Veröffentlicht am 19.12.2023
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsdatum 19.12.2023
Sprache Englisch
Identifikator KITopen-ID: 1000165647
HGF-Programm 46.21.02 (POF IV, LK 01) Cross-Domain ATMLs and Research Groups
Verlag Karlsruher Institut für Technologie (KIT)
Umfang x, 133 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdatum 30.11.2023
Schlagwörter computational geometry, geometric algorithms, Delaunay triangulations, Yao graphs, topographic isolation, algorithm engineering
Referent/Betreuer Sanders, Peter
Funke, Stefan
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page