Robert J. Renka
Abstract
We describe a Fortran-77 software package for constructing a C1 convex surface that interpolates a convex data set consisting of data values at arbitrarily distributed points in the plane (nodes) such that there exists a triangulation of the nodes for which the triangle-based piecewise linear interpolant is convex. The method consists of constructing this data-dependent triangulation, computing a set of nodal gradients for which there exists a convex piecewise linear Hermite interpolant H of the nodal values and gradients, and applying convolution smoothing to H.
Supplemental Material
Available for Download
Software for "CSRFPACK---interpolation of scattered data with a C convexity-preserving surface"
- Carnicer, J. M. 1995. Multivariate convexity preserving interpolation by smooth functions. Advances in Computational Mathematics 3, 395--404.Google Scholar
- Clarkson, K. and Shor, P. 1989. Applications of random sampling in computational geometry, II. Discrete & Computational Geometry 4, 387--421. Google Scholar
- Leung, N. K. and Renka, R. J. 1999. C1 convexity-preserving interpolation of scattered data. SIAM J. Sci. Stat. Comput. 20, 5 (May), 1732--1752. Google Scholar
- Mulmuley, K. 1994. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Inc, Englewood Cliffs, New Jersey.Google Scholar
- Renka, R. J. 1987. Interpolatory tension splines with automatic selection of tension factors. SIAM J. Sci. Stat. Comput. 8, 3 (May), 393--415. Google Scholar
Index Terms
- Algorithm 833: CSRFPACK---interpolation of scattered data with a C1 convexity-preserving surface
Recommendations
C1 Convexity-Preserving Interpolation of Scattered Data
We describe a detailed computational procedure which, given data values at arbitrarily distributed points in the plane, determines if the data are convex and, if so, constructs a smooth convex surface that interpolates the data. The method consists of ...
Algorithm 773: SSRFPACK: interpolation of scattered data on the surface of a sphere with a surface under tension
SSRFPACK is a Fortran 77 software package that constructs a smooth interpolatory or approximating surface to data values associated with arbitrarily distributed points on the surface of a sphere. It employs automatically selected tension factors to ...
Spherical Triangular B-splines with Application to Data Fitting
Triangular B-splines surfaces are a tool for representing arbitrary piecewise polynomial surfaces over planar triangulations, while automatically maintaining continuity properties across patch boundaries. Recently, Alfeld et al. [1] introduced the ...
Reviews
Chenglie Hu
This paper is concerned with a software package, written in Fortran 77, that computes C 1 interpolating surfaces that preserve the convexity of the scattered data. In a little more detail, for a given D={z i} N i-1 and a set of nodes S = {p i = (x i, y i)} N i-1 , a convex surface F is sought to satisfy F(p i) = z i, i = 1, 2, ..., N . As described, the process of constructing such a surface consists of three steps: (1) Constructing a convexity-preserving triangulation T , which is the orthogonal projection of the lower boundary of the convex hull of {(p i, z i)} N i-1 (2) Computing a set of nodal gradients, so that a convex piecewise linear interpolant H(p) can be constructed satisfying H(p i) = z i , and H'(p i) = g i (3) Smoothing out the corners of H , using a convolution smoothing procedure (F(p) = &PHgr; (p - q)H(q)dq for a radial function &PHgr;, evaluated numerically) developed in earlier research. The software pieces are briefly described in the paper. The overall computational cost is O(N 2) , although the triangulation process requires only O(N logN) , as stated above. Existing surface construction methods often address either convexity preservation or interpolation, but rarely both. This software package, together with its underlying theory, is certainly a valuable addition to surface approximation using spline local smoothing techniques, which are not as well understood in higher dimensions. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments