Scattered data fitting by direct extension of local polynomials to bivariate splines

O. Davydov, F. Zeilfelder

Research output: Contribution to journalArticle

36 Citations (Scopus)

Abstract

We present a new scattered data fitting method, where local approximating polynomials are directly extended to smooth (C 1 or C 2) splines on a uniform triangulation (the four-directional mesh). The method is based on designing appropriate minimal determining sets consisting of whole triangles of domain points for a uniformly distributed subset of . This construction allows to use discrete polynomial least squares approximations to the local portions of the data directly as parts of the approximating spline. The remaining Bernstein-Bæ#169;zier coefficients are efficiently computed by extension, i.e., using the smoothness conditions. To obtain high quality local polynomial approximations even for difficult point constellations (e.g., with voids, clusters, tracks), we adaptively choose the polynomial degrees by controlling the smallest singular value of the local collocation matrices. The computational complexity of the method grows linearly with the number of data points, which facilitates its application to large data sets. Numerical tests involving standard benchmarks as well as real world scattered data sets illustrate the approximation power of the method, its efficiency and ability to produce surfaces of high visual quality, to deal with noisy data, and to be used for surface compression.
LanguageEnglish
Pages223-271
Number of pages48
JournalAdvances in Computational Mathematics
Volume21
Issue number3-4
DOIs
Publication statusPublished - Oct 2004

Fingerprint

Scattered Data Fitting
Bivariate Splines
Local Polynomial
Splines
Polynomials
Polynomial Approximation
Spline
Least squares approximations
Polynomial approximation
Triangulation
Least Squares Approximation
Scattered Data
Local Approximation
Computational complexity
Minimal Set
Noisy Data
Singular Values
Voids
Collocation
Large Data Sets

Keywords

  • scattered data fitting
  • bivariate splines
  • four-directional mesh
  • local polynomial least squares approximation
  • Bernstein-Bézier techniques
  • minimal determining set

Cite this

@article{934697bb48d3442dbabf3e32e5ac3056,
title = "Scattered data fitting by direct extension of local polynomials to bivariate splines",
abstract = "We present a new scattered data fitting method, where local approximating polynomials are directly extended to smooth (C 1 or C 2) splines on a uniform triangulation (the four-directional mesh). The method is based on designing appropriate minimal determining sets consisting of whole triangles of domain points for a uniformly distributed subset of . This construction allows to use discrete polynomial least squares approximations to the local portions of the data directly as parts of the approximating spline. The remaining Bernstein-B{\ae}#169;zier coefficients are efficiently computed by extension, i.e., using the smoothness conditions. To obtain high quality local polynomial approximations even for difficult point constellations (e.g., with voids, clusters, tracks), we adaptively choose the polynomial degrees by controlling the smallest singular value of the local collocation matrices. The computational complexity of the method grows linearly with the number of data points, which facilitates its application to large data sets. Numerical tests involving standard benchmarks as well as real world scattered data sets illustrate the approximation power of the method, its efficiency and ability to produce surfaces of high visual quality, to deal with noisy data, and to be used for surface compression.",
keywords = "scattered data fitting, bivariate splines, four-directional mesh, local polynomial least squares approximation, Bernstein-B{\'e}zier techniques, minimal determining set",
author = "O. Davydov and F. Zeilfelder",
year = "2004",
month = "10",
doi = "10.1023/B:ACOM.0000032041.68678.fa",
language = "English",
volume = "21",
pages = "223--271",
journal = "Advances in Computational Mathematics",
issn = "1019-7168",
number = "3-4",

}

Scattered data fitting by direct extension of local polynomials to bivariate splines. / Davydov, O.; Zeilfelder, F.

In: Advances in Computational Mathematics, Vol. 21, No. 3-4, 10.2004, p. 223-271.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Scattered data fitting by direct extension of local polynomials to bivariate splines

AU - Davydov, O.

AU - Zeilfelder, F.

PY - 2004/10

Y1 - 2004/10

N2 - We present a new scattered data fitting method, where local approximating polynomials are directly extended to smooth (C 1 or C 2) splines on a uniform triangulation (the four-directional mesh). The method is based on designing appropriate minimal determining sets consisting of whole triangles of domain points for a uniformly distributed subset of . This construction allows to use discrete polynomial least squares approximations to the local portions of the data directly as parts of the approximating spline. The remaining Bernstein-Bæ#169;zier coefficients are efficiently computed by extension, i.e., using the smoothness conditions. To obtain high quality local polynomial approximations even for difficult point constellations (e.g., with voids, clusters, tracks), we adaptively choose the polynomial degrees by controlling the smallest singular value of the local collocation matrices. The computational complexity of the method grows linearly with the number of data points, which facilitates its application to large data sets. Numerical tests involving standard benchmarks as well as real world scattered data sets illustrate the approximation power of the method, its efficiency and ability to produce surfaces of high visual quality, to deal with noisy data, and to be used for surface compression.

AB - We present a new scattered data fitting method, where local approximating polynomials are directly extended to smooth (C 1 or C 2) splines on a uniform triangulation (the four-directional mesh). The method is based on designing appropriate minimal determining sets consisting of whole triangles of domain points for a uniformly distributed subset of . This construction allows to use discrete polynomial least squares approximations to the local portions of the data directly as parts of the approximating spline. The remaining Bernstein-Bæ#169;zier coefficients are efficiently computed by extension, i.e., using the smoothness conditions. To obtain high quality local polynomial approximations even for difficult point constellations (e.g., with voids, clusters, tracks), we adaptively choose the polynomial degrees by controlling the smallest singular value of the local collocation matrices. The computational complexity of the method grows linearly with the number of data points, which facilitates its application to large data sets. Numerical tests involving standard benchmarks as well as real world scattered data sets illustrate the approximation power of the method, its efficiency and ability to produce surfaces of high visual quality, to deal with noisy data, and to be used for surface compression.

KW - scattered data fitting

KW - bivariate splines

KW - four-directional mesh

KW - local polynomial least squares approximation

KW - Bernstein-Bézier techniques

KW - minimal determining set

U2 - 10.1023/B:ACOM.0000032041.68678.fa

DO - 10.1023/B:ACOM.0000032041.68678.fa

M3 - Article

VL - 21

SP - 223

EP - 271

JO - Advances in Computational Mathematics

T2 - Advances in Computational Mathematics

JF - Advances in Computational Mathematics

SN - 1019-7168

IS - 3-4

ER -