Interpolating Sporadic Data

Abstract

We report here on the problem of estimating a smooth planar curve γ: [0, T ] → ℝ^2 and its derivatives from an ordered sample of interpolation points γ( t _0), γ( t _1),...,γ( t _ i -1),γ( t _ i ),...,γ( t _ m -1),γ( t _ m ), where 0 = t _0 < t _1 <... < t _ i - 1 < t _ i <...< t _ m - 1 < t _ m = T , and the t _ i are not known precisely for 0 < i < m . Such situtation may appear while searching for the boundaries of planar objects or tracking the mass center of a rigid body with no times available. In this paper we assume that the distribution of t _ i coincides with more-or-less uniform sampling . A fast algorithm, yielding quartic convergence rate based on 4-point piecewise-quadratic interpolation is analysed and tested. Our algorithm forms a substantial improvement (with respect to the speed of convergence) of piecewise 3-point quadratic Lagrange intepolation [ 19 ] and [ 20 ]. Some related work can be found in [ 7 ]. Our results may be of interest in computer vision and digital image processing [ 5 ], [ 8 ], [ 13 ], [ 14 ], [ 17 ] or [ 24 ], computer graphics [ 1 ], [ 4 ], [ 9 ], [ 10 ], [ 21 ] or [ 23 ], approximation and complexity theory [ 3 ], [ 6 ], [ 16 ], [ 22 ], [ 26 ] or [ 27 ], and digital and computational geometry [ 2 ] and [ 15 ].