초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

Hershberger and Suri^([1]) proposed an extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions. 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 a...

Hershberger and Suri^([1]) proposed an extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions. 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 Algorithm, produces a path of length at most 2d_P(p,q) in time O(n) joining p and q on the surface of P. But they used the 3-plane wedge to obtain the approximation. In this paper, using a 5-plane wedge, we improve the conventional method so that one can compute a path of length at most 1.415d_P(p,q) joining p and q on the surface of P.