Distance-preserving approximations of polygonal paths
Given a polygonal path P with vertices p1,p2,...,pn and a real number t ≥ 1, a path Q = (pi1, pi2,...,pik) is a t-distance-preserving approximation of P if 1 = i1 < i2 <...< ik = n and each straight-line edge (pij,pij+1) of Q approximates the distance between pij and pij+1 along the path P within a factor of t. We present exact and approximation algorithms that compute such a path Q that minimizes k (when given t) or t (when given k). We also present some experimental results.
|Organisation||Computational Geometry Lab|
Gudmundsson, J. (Joachim), Narasimhan, G. (Giri), & Smid, M. (2003). Distance-preserving approximations of polygonal paths.