Spline Functions on Triangulations (Encyclopedia of Mathematics and its Applications, Series Number 110)

Spline functions are universally recognized as highly effective tools in approximation theory, computer-aided geometric design, image analysis, and numerical analysis. The theory of univariate splines is well known but this text is the first comprehensive treatment of the analogous bivariate theory. A detailed mathematical treatment of polynomial splines on triangulations is outlined, providing a basis for developing practical methods for using splines in numerous application areas. The detailed treatment of the Bernstein-Bézier representation of polynomials will provide a valuable source for researchers and students in CAGD. Chapters on smooth macro-element spaces will allow engineers and scientists using the FEM method to solve partial differential equations numerically with new tools. Workers in the geosciences will find new tools for approximation and data fitting on the sphere. Ideal as a graduate text in approximation theory, and as a source book for courses in computer-aided geometric design or in finite-element methods. Cover......Page 1 About......Page 2 Spline Functions on Triangulations......Page 4 9780521875929......Page 5 Contents......Page 6 Preface......Page 12 1.2. Norms of Polynomials on Triangles......Page 18 1.3. Derivatives of Polynomials......Page 19 1.4. Polynomial Approximation in the Maximum Norm......Page 20 1.5. Averaged Taylor Polynomials......Page 21 1.6. Polynomial Approximation in the q Norm......Page 24 1.7. Approximation on Nonconvex......Page 26 1.8. Interpolation by Bivariate Polynomials......Page 27 1.9. Remarks......Page 32 1.10. Historical Notes......Page 34 2.1. Barycentric Coordinates......Page 35 2.2. Bernstein Basis Polynomials......Page 37 2.3. The B-form......Page 39 2.4. Stability of the B-form Representation......Page 41 2.5. The deCasteljau Algorithm......Page 42 2.6. Directional Derivatives......Page 44 2.7. Derivatives at a Vertex......Page 48 2.8. Cross Derivatives......Page 51 2.9. Computing Coefficients by Interpolation......Page 53 2.10. Conditions for Smooth Joins of Polynomials......Page 55 2.11. Computing Coefficients From Smoothness......Page 58 2.12. The Markov Inequality on Triangles......Page 61 2.13. Integrals and Inner-products of B-polynomials......Page 62 2.14. Subdivision......Page 64 2.16. Dual Bases for the Bernstein Basis Polynomials......Page 66 2.17. A Quasi-interpolant......Page 68 2.18. The Bernstein Approximation Operator......Page 69 2.19. Remarks......Page 74 2.20. Historical Notes......Page 77 3.1. Control Nets and Control Surfaces......Page 79 3.3. Positivity of B-patches......Page 82 3.4. Monotonicity of B-patches......Page 87 3.5. Convexity of B-patches......Page 89 3.6. Control Surfaces and Subdivision......Page 94 3.7. Control Surfaces and Degree Raising......Page 96 3.8. Rendering a B-patch......Page 99 3.11. Historical Notes......Page 101 4.1. Properties of Triangles......Page 103 4.2. Triangulations......Page 104 4.4. Euler Relations......Page 106 4.5. Storing Triangulations......Page 108 4.6. Constructing Triangulations......Page 111 4.7. Clusters of Triangles......Page 113 4.8. Refinements of Triangulations......Page 114 4.9. Optimal Triangulations......Page 120 4.10. Maxmin-Angle Triangulations......Page 121 4.11. Delaunay Triangulations......Page 126 4.12. Constructing Delaunay Triangulations......Page 127 4.13. Type-I and Type-II Triangulations......Page 128 4.14. Quadrangulations......Page 129 4.15. Triangulated Quadrangulations......Page 134 4.16. Nested Sequences of Triangulations......Page 137 4.17. Remarks......Page 138 4.18. Historical Notes......Page 141 5.1. The B-form Representation of Splines......Page 144 5.2. Storing, Evaluating and Rendering Splines......Page 145 5.3. Control Surfaces and the Shape of Spline Surfaces......Page 146 5.4. Dimension and a Local Basis for S^0_d(\bigtriangleup)......Page 147 5.5. Spaces of Smooth Splines......Page 149 5.6. Minimal Determining Sets......Page 152 5.7. Approximation Power of Spline Spaces......Page 154 5.8. Stable Local Bases......Page 158 5.9. Nodal Minimal Determining Sets......Page 160 5.10. Macro-element Spaces......Page 163 5.11. Remarks......Page 164 5.12. Historical Notes......Page 166 6.1. A C^1 Polynomial Macro-element Space......Page 168 6.2. A C^1 Clough-Tocher Macro-element Space......Page 172 6.3. A C^1 Powell–Sabin Macro-element Space......Page 176 6.4. A C^1 Powell–Sabin-12 Macro-element Space......Page 180 6.5. A C^1 Quadrilateral Macro-element Space......Page 183 6.6. Comparison of C^1 Macro-element Spaces......Page 188 6.7. Remarks......Page 189 6.8. Historical Notes......Page 190 7.1. A C^2 Polynomial Macro-element space......Page 191 7.2. A C^2 Clough–Tocher Macro-element Space......Page 195 7.3. A C^2 Powell–Sabin Macro-element Space......Page 199 7.4. A C^2 Wang Macro-element Space......Page 203 7.5. A C^2 Double Clough–Tocher Macro-element......Page 206 7.6. A C^2 Quadrilateral Macro-element Space......Page 209 7.7. Comparison of C^2 Macro-element Spaces......Page 213 7.8. Remarks......Page 214 7.9. Historical Notes......Page 215 8.1. Polynomial Macro-element Spaces......Page 216 8.2. Clough–Tocher Macro-element Spaces......Page 220 8.3. CT Spaces with Natural Degrees of Freedom......Page 226 8.4. Powell–Sabin Macro-element Spaces......Page 231 8.5. PS Spaces with Natural Degrees of Freedom......Page 237 8.6. Quadrilateral Macro-element Spaces......Page 243 8.7. Remarks......Page 248 8.8. Historical Notes......Page 250 9.1. Dimension of Spline Spaces on Cells......Page 251 9.2. Dimension of Superspline Spaces on Cells......Page 255 9.3. Bounds on the Dimension of S^r_d(\bigtriangleup)......Page 257 9.4. Dimension of S^r_d(\bigtriangleup) for d >= 3r + 2......Page 261 9.5. Dimension of Superspline Spaces......Page 266 9.6. Splines on Type-I and Type-II Triangulations......Page 270 9.7. Bounds on the Dimension of Superspline Spaces......Page 272 9.8. Generic Dimension......Page 279 9.9. The Generic Dimension of S^1_3(\bigtriangleup)......Page 282 9.10. Remarks......Page 289 9.11. Historical Notes......Page 291 10.1. Approximation Power......Page 293 10.3. Approximation Power of S^r_d(\bigtriangleup) for d >= 3r + 2......Page 294 10.4. Approximation Power of S^r_d(\bigtriangleup) for d < 3r + 2......Page 303 10.5. Remarks......Page 321 10.6. Historical Notes......Page 323 11.1. Introduction......Page 325 11.2. Supersplines on Four-cells......Page 326 11.3. A Lemma on Near-degenerate Edges......Page 334 11.4. A Stable Local MDS for S^{r,μ}_d(\bigtriangleup)......Page 335 11.5. A Stable MDS for Splines on a Cell......Page 342 11.6. A Stable Local MDS for S^{r,ρ}_d(\bigtriangleup)......Page 344 11.7. Stability and Local Linear Independence......Page 345 11.8. Remarks......Page 348 11.9. Historical Notes......Page 350 12.1. Type-I Box Splines......Page 351 12.2. Type-II Box Splines......Page 360 12.3. Box Spline Series......Page 364 12.4. The Strang–Fix Conditions......Page 368 12.5. Polynomial Reproducing Formulae......Page 372 12.6. Box Spline Quasi-interpolants......Page 376 12.7. Half Box Splines......Page 380 12.8. Finite Shift-invariant Spaces......Page 383 12.9. Remarks......Page 392 12.10. Historical Notes......Page 394 13.1. Spherical Polynomials......Page 395 13.2. Derivatives of Spherical Polynomials......Page 408 13.3. Spherical Triangulations......Page 413 13.4. Spaces of Spherical Splines......Page 414 13.5. Spherical Macro-element Spaces......Page 423 13.6. Remarks......Page 424 13.7. Historical Notes......Page 425 14.2. Projections of Triangulations......Page 426 14.3. Norms on the Sphere......Page 431 14.4. Spherical Sobolev Spaces......Page 433 14.5. Sobolev Seminorms......Page 436 14.6. Clusters of Spherical Triangles......Page 438 14.7. Local Approximation by Spherical Polynomials......Page 440 14.8. The Markov Inequality for Spherical Polynomials......Page 441 14.9. Spaces with Full Approximation Power......Page 442 14.10. Remarks......Page 449 14.11. Historical Notes......Page 450 15.1. The Space P_d......Page 451 15.2. Barycentric Coordinates......Page 452 15.3. Bernstein Basis Polynomials......Page 454 15.4. The B-form of a Trivariate Polynomial......Page 455 15.5. Stability of the B-form......Page 457 15.6. The de Casteljau Algorithm......Page 458 15.7. Directional Derivatives......Page 459 15.8. B-coefficients and Derivatives at a Vertex......Page 460 15.9. B-coefficients and Derivatives on Edges......Page 463 15.10. B-coefficients and Derivatives on Faces......Page 466 15.11. B-Coefficients and Hermite Interpolation......Page 468 15.13. Integrals and Inner-products......Page 469 15.14. Conditions for Smooth Joins......Page 470 15.15. Approximation Power in the Maximum Norm......Page 471 15.16. Averaged Taylor Polynomials......Page 472 15.17. Approximation Power in the q-Norms......Page 473 15.18. Subdivision......Page 474 15.20. Remarks......Page 475 15.21. Historical Notes......Page 477 16.1. Properties of a Tetrahedron......Page 478 16.2. General Tetrahedral Partitions......Page 480 16.3. Regular Tetrahedral Partitions......Page 481 16.4. Euler Relations......Page 482 16.5. Constructing and Storing Tetrahedral Partitions......Page 486 16.6. Clusters of Tetrahedra......Page 487 16.7. Refinements of Tetrahedral Partitions......Page 489 16.9. Remarks......Page 496 16.10 Historical Notes......Page 497 17.1. C^0 Trivariate Spline Spaces......Page 498 17.2. Spaces of Smooth Splines......Page 500 17.3. Minimal Determining Sets......Page 501 17.4. Approximation Power of Trivariate Spline Spaces......Page 503 17.5. Stable Local Bases......Page 506 17.6. Nodal Minimal Determining Sets......Page 507 17.7. Hermite Interpolation......Page 509 17.8. Dimension of Trivariate Spline Spaces......Page 511 17.9. Remarks......Page 516 17.10. Historical Notes......Page 517 18.1. Introduction......Page 519 18.2. A C^1 Polynomial Macro-element......Page 520 18.3. A C^1 Macro-element on the Alfeld Split......Page 525 18.4. A C^1 Macro-element on the Worsey–Farin Split......Page 530 18.5. A C^1 Macro-element on the Worsey–Piper Split......Page 534 18.6. A C^2 Polynomial Macro-element......Page 537 18.7. A C^2 Macro-element on the Alfeld Split......Page 541 18.8. A C^2 Macro-element on the Worsey–Farin Split......Page 547 18.9. Another C^2 Worsey–Farin Macro-element......Page 554 18.10. A C^2 Macro-element on the Alfeld-16 Split......Page 561 18.11. A C^r Polynomial Macro-element......Page 565 18.12. Remarks......Page 574 18.13. Historical Notes......Page 575 References......Page 576 Index......Page 604

Spline functions are universally recognized as highly effective tools in approximation theory, computer-aided geometric design, image analysis, and numerical analysis. The theory of univariate splines is well known but this text is the first comprehensive treatment of the analogous bivariate theory. A detailed mathematical treatment of polynomial splines on triangulations is outlined, providing a basis for developing practical methods for using splines in numerous application areas. The detailed treatment of the Bernstein-Bézier representation of polynomials will provide a valuable source for researchers and students in CAGD. Chapters on smooth macro-element spaces will allow engineers and scientists using the FEM method to solve partial differential equations numerically with new tools. Workers in the geosciences will find new tools for approximation and data fitting on the sphere. Ideal as a graduate text in approximation theory, and as a source book for courses in computer-aided geometric design or in finite-element methods.

Spline functions are universally recognized as highly effective tools in approximation theory, computer-aided geometric design, image analysis, and numerical analysis. The theory of univariate splines is well known but this text is the first comprehensive treatment of the analogous bivariate theory. A detailed mathematical treatment of polynomial splines on triangulations is outlined, providing a basis for developing practical methods for using splines in numerous application areas. The detailed treatment of the Bernstein-Bezier representation ..