{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T06:51:23Z","timestamp":1791355883708,"version":"4.3.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,4,1]],"date-time":"2006-04-01T00:00:00Z","timestamp":1143849600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2006,4]]},"abstract":"<jats:p>\n                    Computing a curve to approximate data points is a problem encountered frequently in many applications in computer graphics, computer vision, CAD\/CAM, and image processing. We present a novel and efficient method, called\n                    <jats:italic>squared distance minimization<\/jats:italic>\n                    (SDM), for computing a planar B-spline curve, closed or open, to approximate a target shape defined by a\n                    <jats:italic>point cloud<\/jats:italic>\n                    , that is, a set of unorganized, possibly noisy data points. We show that SDM significantly outperforms other optimization methods used currently in common practice of curve fitting. In SDM, a B-spline curve starts from some properly specified initial shape and converges towards the target shape through iterative quadratic minimization of the fitting error. Our contribution is the introduction of a new fitting error term, called the\n                    <jats:italic>squared distance (SD) error term<\/jats:italic>\n                    , defined by a curvature-based quadratic approximant of squared distances from data points to a fitting curve. The SD error term faithfully measures the geometric distance between a fitting curve and a target shape, thus leading to faster and more stable convergence than the point distance (PD) error term, which is commonly used in computer graphics and CAGD, and the tangent distance (TD) error term, which is often adopted in the computer vision community. To provide a theoretical explanation of the superior performance of SDM, we formulate the B-spline curve fitting problem as a nonlinear least squares problem and conclude that SDM is a quasi-Newton method which employs a curvature-based positive definite approximant to the true Hessian of the objective function. Furthermore, we show that the method based on the TD error term is a Gauss-Newton iteration, which is unstable for target shapes with high curvature variations, whereas optimization based on the PD error term is the alternating method that is known to have linear convergence.\n                  <\/jats:p>","DOI":"10.1145\/1138450.1138453","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T10:14:26Z","timestamp":1153822466000},"page":"214-238","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":322,"title":["Fitting B-spline curves to point clouds by curvature-based squared distance minimization"],"prefix":"10.1145","volume":"25","author":[{"given":"Wenping","family":"Wang","sequence":"first","affiliation":[{"name":"University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Helmut","family":"Pottmann","sequence":"additional","affiliation":[{"name":"Vienna University of Technology, Wien, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yang","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02922668"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(94)90303-4"},{"key":"e_1_2_1_3_1","unstructured":"Bjorck A. 1996. Numerical Methods for Least Squares Problems. Mathematics Society for Industrial and Applied Mathematics Philadelphia PA. Bjorck A. 1996. Numerical Methods for Least Squares Problems. Mathematics Society for Industrial and Applied Mathematics Philadelphia PA."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Blake A. and Isard M. 1998. Active Contours. Springer Verlag New York NY. Blake A. and Isard M. 1998. Active Contours. Springer Verlag New York NY.","DOI":"10.1007\/978-1-4471-1555-7"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/566282.566303"},{"key":"e_1_2_1_6_1","unstructured":"Farin G. 1997. Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide 4th Ed. Academic Press New York NY. Farin G. 1997. Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide 4th Ed. Academic Press New York NY."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/221659.221665"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-003-0046-y"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/353981.353992"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/gmod.2001.0542"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of Visualization. 341--348","author":"Haber J."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237216"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192233"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(88)90017-9"},{"key":"e_1_2_1_15_1","unstructured":"Hoschek J. and Lasser D. 1993. Fundamentals of Computer Aided Geometric Design. AK Peters. Hoschek J. and Lasser D. 1993. Fundamentals of Computer Aided Geometric Design. AK Peters."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2004.12.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00133570"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Kelley C. T. 1999. Iterative Methods for Optimization. Society for Industrial and Applied Mathematics Philadelphia PA. Kelley C. T. 1999. Iterative Methods for Optimization. Society for Industrial and Applied Mathematics Philadelphia PA.","DOI":"10.1137\/1.9781611970920"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Laurent-Gengoux P. and Mekhilef M. 1993. Optimization of a nurbs representation. Comput.-aided Design 25 699--710. Laurent-Gengoux P. and Mekhilef M. 1993. Optimization of a nurbs representation. Comput.-aided Design 25 699--710.","DOI":"10.1016\/0010-4485(93)90011-C"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(89)90003-1"},{"key":"e_1_2_1_21_1","unstructured":"Luenberger D. 1984. Linear and Nonlinear Programming. Addision-Wesley. Luenberger D. 1984. Linear and Nonlinear Programming. Addision-Wesley."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Ma W. Y. and Kruth J. P. 1995. Parameterization of randomly measured points for least squares fitting of b-spline curves and surfaces. Comput.-aided Design 27 663--675. Ma W. Y. and Kruth J. P. 1995. Parameterization of randomly measured points for least squares fitting of b-spline curves and surfaces. Comput.-aided Design 27 663--675.","DOI":"10.1016\/0010-4485(94)00018-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1077-3169(02)00006-0"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.368173"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Osher S. and Fedkiw. 2003. Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag New York NY. Osher S. and Fedkiw. 2003. Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag New York NY.","DOI":"10.1007\/b98879"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/357314.357315"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/964967.801153"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Pottmann H. and Hofer M. 2003. Geometry of the squared distance function to curves and surfaces. In Visualization and Mathematics III H. Hege and K. Polthier Eds. 223--244. Pottmann H. and Hofer M. 2003. Geometry of the squared distance function to curves and surfaces. In Visualization and Mathematics III H. Hege and K. Polthier Eds. 223--244.","DOI":"10.1007\/978-3-662-05105-4_12"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of Pacific Graphics. IEEE Computer Society Press, 8--25","author":"Pottmann H."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Pottmann H. and Wallner J. 2001. Computational Line Geometry. Springer-Verlag Berlin Germany. Pottmann H. and Wallner J. 2001. Computational Line Geometry. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-3-642-04018-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/325334.325225"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1022057"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8396(91)90016-5"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2003.06.004"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Sethian J. A. 1999. Level Set Methods and Fast Marching Methods. Cambridge University Press Cambridge UK. Sethian J. A. 1999. Level Set Methods and Fast Marching Methods. Cambridge University Press Cambridge UK.","DOI":"10.1137\/S0036144598347059"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(98)00024-7"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/gmod.2002.0571"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/108541.108548"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/545261.545283"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8396(01)00086-3"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Yang H. P. Wang W. and Sun J. G. 2004. Control point adjustment for b-spline curve approximation. Comput.-aided Design 36 639--652. Yang H. P. Wang W. and Sun J. G. 2004. Control point adjustment for b-spline curve approximation. Comput.-aided Design 36 639--652.","DOI":"10.1016\/S0010-4485(03)00140-4"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1138450.1138453","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1138450.1138453","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:06:27Z","timestamp":1750244787000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1138450.1138453"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["10.1145\/1138450.1138453"],"URL":"https:\/\/doi.org\/10.1145\/1138450.1138453","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,4]]},"assertion":[{"value":"2006-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}