descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Article , Conference object 01 Jan 2009Embargo end date: 23 Jun 2009 English Publisher:Springer Berlin HeidelbergJournal:Algorithmica, volume 69, pages 58-77 (issn: 0178-4617, eissn: 1432-0541,

Authors: Wenk, Carola; Cook, Atlas F.;

doi: 10.1007/978-3-642-03367-4_14 , 10.1007/s00453-012-9723-6 , 10.4230/dagsemproc.09111.5

Shortest Path Problems on a Polyhedral Surface

- Summary
- Subjects
- Metrics

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.

Related Organizations

Leibniz Association
Germany
The University of Texas at San Antonio
United States
The University of Texas System
United States
Schloss Dagstuhl – Leibniz Center for Informatics
Germany
Tulane University
United States

View all View all

Keywords

000, Shortest paths, edge sequences, 004, ddc: ddc:004

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	10
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%