Distance-preserving approximations of polygonal paths
- Gudmundsson, Joachim
- Narasimhan, Giri
- Smid, Michiel
Publication date
April 2007
DOI Publisher
Elsevier B.V. ISSN
0925-7721 Citation count (estimate)
17Abstract
AbstractGiven a polygonal path P with vertices p1,p2,…,pn∈Rd 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
Add to ORKG