Polyline fitting of planar points under min-sum criteria

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

doi:10.1142/S0218195906001951

Polyline fitting of planar points under min-sum criteria

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

Research output: Contribution to journal › Article › peer-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 ₁- and L₂-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 language	English (US)
Pages (from-to)	97-116
Number of pages	20
Journal	International Journal of Computational Geometry and Applications
Volume	16
Issue number	2-3
DOIs	https://doi.org/10.1142/S0218195906001951
State	Published - 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

Access to Document

10.1142/S0218195906001951

Cite this

@article{4b3c04e5858744d4a02d18ff843f848a,

title = "Polyline fitting of planar points under min-sum criteria",

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.",

keywords = "Algorithms, Computational geometry, Parametric searching, Polyline fitting, Polynomial time approximation scheme, Regression analysis",

author = "Boris Aronov and Tetsuo Asano and Naoki Katoh and Kurt Mehlhorn and Takeshi Tokuyama",

note = "Funding Information: 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\- and L2-metrics, which are more appro priate measures than uniform and Hausdorff metrics in statistical context. We present *Supported in part by NSF ITR Grant CCR-00-81964. Part of the work was B.A. was visiting JAIST, Universitat Politecnica de Catalunya, and MPII. tPartially supported by the Ministry of Education, Science, Sports and Culture, Scientific Research (B).",

year = "2006",

month = jun,

doi = "10.1142/S0218195906001951",

language = "English (US)",

volume = "16",

pages = "97--116",

journal = "International Journal of Computational Geometry and Applications",

issn = "0218-1959",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "2-3",

}

TY - JOUR

T1 - Polyline fitting of planar points under min-sum criteria

AU - Aronov, Boris

AU - Asano, Tetsuo

AU - Katoh, Naoki

AU - Mehlhorn, Kurt

AU - Tokuyama, Takeshi

N1 - Funding Information: 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\- and L2-metrics, which are more appro priate measures than uniform and Hausdorff metrics in statistical context. We present *Supported in part by NSF ITR Grant CCR-00-81964. Part of the work was B.A. was visiting JAIST, Universitat Politecnica de Catalunya, and MPII. tPartially supported by the Ministry of Education, Science, Sports and Culture, Scientific Research (B).

PY - 2006/6

Y1 - 2006/6

N2 - 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.

AB - 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.

KW - Algorithms

KW - Computational geometry

KW - Parametric searching

KW - Polyline fitting

KW - Polynomial time approximation scheme

KW - Regression analysis

UR - http://www.scopus.com/inward/record.url?scp=33646507892&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646507892&partnerID=8YFLogxK

U2 - 10.1142/S0218195906001951

DO - 10.1142/S0218195906001951

M3 - Article

AN - SCOPUS:33646507892

SN - 0218-1959

VL - 16

SP - 97

EP - 116

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 2-3

ER -

Polyline fitting of planar points under min-sum criteria

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this