POLYLINE FITTING OF PLANAR POINTS UNDER MIN-SUM CRITERIA
Boris S. Aronov, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama · International Journal of Computational Geometry & Applications · 2006
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum criteria with respect to L1- and L2-metrics, which are more appropriate measures than uniform and Hausdorff metrics in statistical context. We present efficient algorithms for the 1-joint versions of the problem and fully polynomial-time approximation schemes for the general k-joint versions.