Discrete smooth interpolation

ABSTRACT

Interpolation of a function ƒ (.) known at some data points of RP is a common problem. Many computer applications (e.g., automatic contouring) need to perform interpolation only at the nodes of a given grid. Whereas most classical methods solve the problem by finding a function defined everywhere, the proposed method avoids explicitly computing such a function and instead produces values only at the grid points. For two-dimensional regular grids, a special case of this method is identical to the Briggs method (see “Machine Contouring Using Minimum Curvature,” Geophysics 17, 1 (1974)), while another special case is equivalent to a discrete version of thin plate splines (see J. Duchon, Fonctions Splines du type Plaque Mince en Dimention 2, Séminaire d'analyse numérique, n 231, U.S.M.G., Grenoble, 1975; and J. Enriquez, J. Thomann, and M. Goupillot, Application of bidimensional spline functions to geophysics, Geophysics 48, 9 (1983)).

REFERENCES

• 1: Hiroshi Akima, A New Method of Interpolation and Smooth Curve Fitting Based on Local Procedures, Journal of the ACM (JACM), v.17 n.4, p.589-602, Oct. 1970 [doi>10.1145/321607.321609]
• 2: Hiroshi Akima, Algorithm 433: interpolation and smooth curve fitting based on local procedures [E2], Communications of the ACM, v.15 n.10, p.914-918, Oct. 1972 [doi>10.1145/355604.355605]
• 3: Hiroshi Akima, A method of bivariate interpolation and smooth surface fitting based on local procedures, Communications of the ACM, v.17 n.1, p.18-20, Jan. 1974 [doi>10.1145/360767.360779]
• 4: BRIGGS, I.C. Machine contouring using minimum curvature. Geophysics 17, 1 (1974).
• 5: DUBRULE, O., AND KOSTOV, C. An interpolation method taking into account inequality constraints: I. Methodology. Math. Geol. 18, 1 (1986), 33-51.
• 6: DUCHON, J. l~bnctions Splines du Type Plaque Mince en Dimension 2. S6minaire d'analyse num6rique, n 2:31, U.S.M.G., Grenoble, 1975.
• 7: ENRIQUEZ, J., THOMANN, J., AND GOUPILLOT, M. Application ofbidimensional spline functions to geophysics. Geophysics 48, 9 (1983).
• 8: G Farin, Triangular Berstein-Be´zier patches, Computer Aided Geometric Design, v.3 n.2, p.83-127, August 1986 [doi>10.1016/0167-8396(86)90016-6]
• 9: G,LI~, P. E., MURRAY(, W., AND WRIGHT, M.H. Practical Optimisation. Academic Press, New York, 1981.
• 10: GOLUB, G., AND LOAN, V. Matrix Computation. The Johns Hopkins University Press, Baltimore, Md., 1983.
• 11: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 12: JOURNEI,, A.G. Constrained interpolation and qualitative information. The soft kriging approach. Math. Geol. 18, 3 (1986), 269-286.
• 13: JOURNEI., A. G., AND HUIJBREGTS, C. J. Mining Geostatisties. Academic Press, New York, 1978.
• 14: KOSTOV, C., AND DUBRULE, O. An interpolation method taking into account inequality constraints: II. Practical Approach. Math. Geol. I8, 2 (1986), 53-73.
• 15: LUENBERGER, D. G. Introduction to Linear and Non Linear Programming. Addison-Wesley, Reading, Mass., 1973.
• 16: MALI,ET, J.L. Automatic contouring in presence of discontinuities. Geostatistics for Natural Resources Characterization, Part 2, G. Verly, M. David, A. G. Jourmel, and M. Marechal, Eds. Reidel, Hingham, Mass., 1984, 669-677.
• 17: MALLET, J. L., JACQUEMIN, P., AND ROYER, J.J. Interactive computer aided design in the processing of mining and geological data. In The Role o1' Data in Scientific Progress, CODA TA 1985, P. F. Glaeser, Ed. Elsevier North-Holland, New York, pp. 19-24.
• 18: MATHERON, G. Les Variables R@ionalis~es et Leur Estimation. Masson, Paris, 1965.
• 19: MATHERON, (}. Spline and kriging, their formal equivalence. Geol. Contrib. (Syracuse Univ.) (198I).
• 20: Michael E. Mortenson, Geometric modeling, John Wiley & Sons, Inc., New York, NY, 1985
• 21: Donald Shepard, A two-dimensional interpolation function for irregularly-spaced data, Proceedings of the 1968 23rd ACM national conference, p.517-524, August 27-29, 1968 [doi>10.1145/800186.810616]
• 22: YOUNG, D.M. Iterative Solution of Large Linear Systems. Academic Press, New York, 1971.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Interpolation formulas

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Smoothing

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Theory