Length Estimation for Curves with Different Samplings

Abstract

This paper looks at the problem of approximating the length of the unknown parametric curve ⋎ [0,1] → IRⁿ from points qᵢ = ⋎ (tᵢ), where the parameters ti are not given. When the tᵢ are uniformly distributed Lagrange interpolation by piecewise polynomials provides efficient length estimates, but in other cases this method can behave very badly [15]. In the present paper we apply this simple algorithm when the tᵢ are sampled in what we call an ε-uniform fashion, where 0 ≤ ε ≤ 1. Convergence of length estimates using Lagrange interpolants is not as rapid as for uniform sampling, but better than for some of the examples of [15]. As a side-issue we also consider the task of approximating ⋎ up to parameterization, and numerical experiments are carried out to investigate sharpness of our theoretical results. The results may be of interest in computer vision, computer graphics, approximation and complexity theory, digital and computational geometry, and digital image analysis.