Polyline fitting of planar points under min-sum criteria

Boris Aronov, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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 L 1- and L2-metrics, which are more appropriate measures than uniform and Hausdorff metrics in statistical context. We presentefficient algorithms for the 1-joint versions of the problem and fully polynomial-time approximation schemes for the general k-joint versions.

    Original languageEnglish (US)
    Pages (from-to)97-116
    Number of pages20
    JournalInternational Journal of Computational Geometry and Applications
    Volume16
    Issue number2-3
    DOIs
    StatePublished - Jun 2006

    Keywords

    • Algorithms
    • Computational geometry
    • Parametric searching
    • Polyline fitting
    • Polynomial time approximation scheme
    • Regression analysis

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Theory and Mathematics
    • Computational Mathematics
    • Applied Mathematics

    Fingerprint Dive into the research topics of 'Polyline fitting of planar points under min-sum criteria'. Together they form a unique fingerprint.

    Cite this