Shortest paths on a polyhedron

descriptionPublicationkeyboard_double_arrow_right Article , Conference object 01 Jan 1990Publisher:ACM PressJournal:Proceedings of the sixth annual symposium on Computational geometry - SCG '90

Authors: Jindong Chen; Yijie Han;

doi: 10.1145/98524.98601

Shortest paths on a polyhedron

- Summary
- Metrics

Abstract

We present an algorithm for determining the shortest path between a source point and any destination point along the surface of a polyhedron (need not be convex). Our algorithm uses a new approach which deviates from the conventional “continuous Dijkstra” technique. It takes O(n2) time and o(n) space to determine the shortest path and to compute the inward layout which can be used to construct a structure for processing queries of shortest path from the source point to any destination point.

Related Organizations

University of Kentucky
United States

Impact byBIP!

	selected citations These citations are derived from selected sources. 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).	143
	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.	Top 1%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%