DagSemProc.09111.5.pdf
- Filesize: 369 kB
- 30 pages
Document
Shortest Path Problems on a Polyhedral Surface
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 9111
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2009-06-23
Cite As Get BibTex
Carola Wenk and Atlas F. Cook. Shortest Path Problems on a Polyhedral Surface. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/DagSemProc.09111.5
Abstract
We develop algorithms to compute edge sequences, Voronoi diagrams, shortest path maps, the Fréchet distance, and the diameter for a polyhedral surface. Distances on the surface are measured either by the length of a Euclidean shortest path or by link distance. Our main result is a linear-factor speedup for computing all shortest path edge sequences on a convex polyhedral surface.
Subject Classification
Keywords
- Shortest paths
- edge sequences
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads