Distance-preserving approximations of polygonal paths (Q868106)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Distance-preserving approximations of polygonal paths |
scientific article |
Statements
Distance-preserving approximations of polygonal paths (English)
0 references
19 February 2007
0 references
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.
0 references
path simplification
0 references
\(t\)-spanners
0 references
well-separated pair decomposition
0 references
experimental algorithms
0 references
numerical examples
0 references
minimum number of vertices
0 references