Distance-preserving approximations of polygonal paths (Q868106)

Given a polygonal path \(P\) with vertices \(p_{1},p_{2},\dots,p_{n}\in\mathbb R^d\) and a real number \(t\geq1\), a path \(Q=(p_{i_1},p_{i_2},\dots,p_{i_k})\) is a \(t\)-distance-preserving approximation of \(P\) if \(1=i_1<i_2<\dots<i_k=n\) and each straight-line edge \((p_{i_j},p_{i_{j+1}})\) of \(Q\) approximates the distance between \(p_{i_j}\) and \(p_{i_{j+1}}\) along the path \(P\) within a factor of \(t\). The following two problems about a polygonal path \(P\) with \(n\) vertices are considered in this paper: a) Given real number \(t\geq1\), compute a \(t\)-distance-preserving approximation of \(P\) having the minimum number of vertices; b) Given integer \(k\) with \(2\leq k\leq n\), compute the minimum value of \(t\) for which a \(t\)-distance-preserving approximation of \(P\) having at most \(k\) vertices exists. The authors present exact and approximation algorithms that compute such a path \(Q\) that minimizes \(k\) (when given \(t\)) or \(t\) (when given \(k\)). They also present some experimental results.