Shortest paths on polyhedral surfaces and terrains

Siu Wing Cheng; Jiongxin Jin

doi:10.1145/2591796.2591821

Shortest paths on polyhedral surfaces and terrains

Siu Wing Cheng, Jiongxin Jin

Department of Computer Science and Engineering

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

10 Citations (Scopus)

Abstract

We present an algorithm for computing shortest paths on polyhedral surfaces under convex distance functions. Let n be the total number of vertices, edges and faces of the surface. Our algorithm can be used to compute L₁ and L_∞ shortest paths on a polyhedral surface in O(n² log⁴ n) time. Given an ε ∈ (0, 1), our algorithm can find (1 + ε)- approximate shortest paths on a terrain with gradient constraints and under cost functions that are linear combinations of path length and total ascent. The running time is O (1/√εn² log n + n ² log⁴ n ". This is the first efficient PTAS for such a general setting of terrain navigation.

Original language	English
Title of host publication	STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing
Publisher	Association for Computing Machinery
Pages	373-382
Number of pages	10
ISBN (Print)	9781450327107
DOIs	https://doi.org/10.1145/2591796.2591821
Publication status	Published - 2014
Event	4th Annual ACM Symposium on Theory of Computing, STOC 2014 - New York, NY, United States Duration: 31 May 2014 → 3 Jun 2014

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)	0737-8017

Conference

Conference	4th Annual ACM Symposium on Theory of Computing, STOC 2014
Country/Territory	United States
City	New York, NY
Period	31/05/14 → 3/06/14

Keywords

Convex distance function
Polyhedral surface
Shortest path
Terrain

Access to Document

10.1145/2591796.2591821

Cite this

@inproceedings{2c5f8a86ee084b339849f00a233f33c0,

title = "Shortest paths on polyhedral surfaces and terrains",

abstract = "We present an algorithm for computing shortest paths on polyhedral surfaces under convex distance functions. Let n be the total number of vertices, edges and faces of the surface. Our algorithm can be used to compute L1 and L∞ shortest paths on a polyhedral surface in O(n2 log4 n) time. Given an ε ∈ (0, 1), our algorithm can find (1 + ε)- approximate shortest paths on a terrain with gradient constraints and under cost functions that are linear combinations of path length and total ascent. The running time is O (1/√εn2 log n + n 2 log4 n {"}. This is the first efficient PTAS for such a general setting of terrain navigation.",

keywords = "Convex distance function, Polyhedral surface, Shortest path, Terrain",

author = "Cheng, \{Siu Wing\} and Jiongxin Jin",

year = "2014",

doi = "10.1145/2591796.2591821",

language = "English",

isbn = "9781450327107",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "373--382",

booktitle = "STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing",

note = "4th Annual ACM Symposium on Theory of Computing, STOC 2014 ; Conference date: 31-05-2014 Through 03-06-2014",

}

Cheng, SW & Jin, J 2014, Shortest paths on polyhedral surfaces and terrains. in STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 373-382, 4th Annual ACM Symposium on Theory of Computing, STOC 2014, New York, NY, United States, 31/05/14. https://doi.org/10.1145/2591796.2591821

Shortest paths on polyhedral surfaces and terrains. / Cheng, Siu Wing; Jin, Jiongxin.
STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing. Association for Computing Machinery, 2014. p. 373-382 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

T1 - Shortest paths on polyhedral surfaces and terrains

AU - Cheng, Siu Wing

AU - Jin, Jiongxin

PY - 2014

Y1 - 2014

N2 - We present an algorithm for computing shortest paths on polyhedral surfaces under convex distance functions. Let n be the total number of vertices, edges and faces of the surface. Our algorithm can be used to compute L1 and L∞ shortest paths on a polyhedral surface in O(n2 log4 n) time. Given an ε ∈ (0, 1), our algorithm can find (1 + ε)- approximate shortest paths on a terrain with gradient constraints and under cost functions that are linear combinations of path length and total ascent. The running time is O (1/√εn2 log n + n 2 log4 n ". This is the first efficient PTAS for such a general setting of terrain navigation.

AB - We present an algorithm for computing shortest paths on polyhedral surfaces under convex distance functions. Let n be the total number of vertices, edges and faces of the surface. Our algorithm can be used to compute L1 and L∞ shortest paths on a polyhedral surface in O(n2 log4 n) time. Given an ε ∈ (0, 1), our algorithm can find (1 + ε)- approximate shortest paths on a terrain with gradient constraints and under cost functions that are linear combinations of path length and total ascent. The running time is O (1/√εn2 log n + n 2 log4 n ". This is the first efficient PTAS for such a general setting of terrain navigation.

KW - Convex distance function

KW - Polyhedral surface

KW - Shortest path

KW - Terrain

UR - https://www.webofscience.com/wos/woscc/full-record/WOS:000485547000039

UR - https://openalex.org/W2080237972

UR - https://www.scopus.com/pages/publications/84904277421

U2 - 10.1145/2591796.2591821

DO - 10.1145/2591796.2591821

M3 - Conference Paper published in a book

SN - 9781450327107

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 373

EP - 382

BT - STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 2014

Y2 - 31 May 2014 through 3 June 2014

ER -

Shortest paths on polyhedral surfaces and terrains

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this