Analysis for shortest path algorithm on convex polytope in E3

Young Soo Lee; Eun Seok Lee

doi:10.1049/el:20001317

Analysis for shortest path algorithm on convex polytope in E³

Young Soo Lee
, Eun Seok Lee

Department of Computer Science and Engineering

Sungkyunkwan University

Research output: Contribution to journal › Article › peer-review

Abstract

Hershberger and Suri proposed an extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions in 1998. Given a convex polytope P with n vertices and two points p, q on its surface, let d_p(p, q) denote the shortest path distance between p and q on the surface of P. Their algorithm, ShortestPath, produces a path of length at most 2d_p(p, q) in time O(n). This algorithm is revised, and achieves a ratio of 1.786.

Original language	English
Pages (from-to)	1895-1897
Number of pages	3
Journal	Electronics Letters
Volume	36
Issue number	22
DOIs	https://doi.org/10.1049/el:20001317
State	Published - 26 Oct 2000

Access to Document

10.1049/el:20001317

Cite this

@article{f7490ae7f45b4a07b6b96895450a317c,

title = "Analysis for shortest path algorithm on convex polytope in E3",

abstract = "Hershberger and Suri proposed an extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions in 1998. Given a convex polytope P with n vertices and two points p, q on its surface, let dp(p, q) denote the shortest path distance between p and q on the surface of P. Their algorithm, ShortestPath, produces a path of length at most 2dp(p, q) in time O(n). This algorithm is revised, and achieves a ratio of 1.786.",

author = "Lee, \{Young Soo\} and Lee, \{Eun Seok\}",

year = "2000",

month = oct,

day = "26",

doi = "10.1049/el:20001317",

language = "English",

volume = "36",

pages = "1895--1897",

journal = "Electronics Letters",

issn = "0013-5194",

publisher = "John Wiley \& Sons Inc.",

number = "22",

}

TY - JOUR

T1 - Analysis for shortest path algorithm on convex polytope in E3

AU - Lee, Young Soo

AU - Lee, Eun Seok

PY - 2000/10/26

Y1 - 2000/10/26

N2 - Hershberger and Suri proposed an extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions in 1998. Given a convex polytope P with n vertices and two points p, q on its surface, let dp(p, q) denote the shortest path distance between p and q on the surface of P. Their algorithm, ShortestPath, produces a path of length at most 2dp(p, q) in time O(n). This algorithm is revised, and achieves a ratio of 1.786.

AB - Hershberger and Suri proposed an extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions in 1998. Given a convex polytope P with n vertices and two points p, q on its surface, let dp(p, q) denote the shortest path distance between p and q on the surface of P. Their algorithm, ShortestPath, produces a path of length at most 2dp(p, q) in time O(n). This algorithm is revised, and achieves a ratio of 1.786.

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

U2 - 10.1049/el:20001317

DO - 10.1049/el:20001317

M3 - Article

AN - SCOPUS:0034295271

SN - 0013-5194

VL - 36

SP - 1895

EP - 1897

JO - Electronics Letters

JF - Electronics Letters

IS - 22

ER -

Analysis for shortest path algorithm on convex polytope in E³

Abstract

Access to Document

Other files and links

Fingerprint

Cite this