A two-dimensional interpolation function for irregularly-spaced data

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A two-dimensional interpolation function for irregularly-spaced data

Full text

Pdf (622 KB)

Source

ACM Annual Conference/Annual Meeting archive
Proceedings of the 1968 23rd ACM national conference table of contents

Pages: 517 - 524

Year of Publication: 1968

Author

Donald Shepard

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 96, Downloads (12 Months): 813, Citation Count: 84

Additional Information:

abstract references cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800186.810616 What is a DOI?

ABSTRACT

In many fields using empirical areal data there arises a need for interpolating from irregularly-spaced data to produce a continuous surface. These irregularly-spaced locations, hence referred to as “data points,” may have diverse meanings: in meterology, weather observation stations; in geography, surveyed locations; in city and regional planning, centers of data-collection zones; in biology, observation locations. It is assumed that a unique number (such as rainfall in meteorology, or altitude in geography) is associated with each data point. In order to display these data in some type of contour map or perspective view, to compare them with data for the same region based on other data points, or to analyze them for extremes, gradients, or other purposes, it is extremely useful, if not essential, to define a continuous function fitting the given values exactly. Interpolated values over a fine grid may then be evaluated. In using such a function it is assumed that the original data are without error, or that compensation for error will be made after interpolation.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P SWITZER C M MOHR R E HEITMAN Statistical analyses of ocean terrain and contour plotting procedures Project Trident Report 1440464 Arthur D Little Inc April 1964
	2	J F STEFFENSEN Interpolation Williams and Wilkins Baltimore 1927 Chap 19
	3	I S BEREZIN N P ZHIDKOV Computing methods Addison-Wesley Publishing Company Inc Reading Mass 1965 Vol I Chap 2
	4	C deBOOR Bicubic spline interpolation J Math and Phys 41 212-218 1962
	5	A DOWNING The automatic construction of contour plots with applications to numerical analysis research Defense Documentation Center Report AD 649811 January 1966
	6	W R TOBLER An interpolation algorithm for geographical data University of Michigan undated
	7	W C KRUMBEIN Trend surface analysis of contour-type maps with irregular control point spacing J Geophys Re 64 823-834 1959
	8	B E BENGTSSON S NORDBECK Construction of isarithms and isarithmic maps by computers University of Lund Sweden BIT 4 87-105 1964
	9	A H SCHMIDT SYMAP A user's manual Tri-County Regional Planning Commission Lansing Michigan May 1966
	10	User's reference manual for synagraphic computer mapping 'SYMAP' version V Laboratory for Computer Graphics Harvard Univ June 1968

CITED BY 86

	Arnold Neumaier, Rational Functions with Prescribed Global and Local Minimizers, Journal of Global Optimization, v.25 n.2, p.175-181, February 2003
	Robert J. Renka, Multivariate interpolation of large sets of scattered data, ACM Transactions on Mathematical Software (TOMS), v.14 n.2, p.139-148, June 1988
	Holger Wendland, Moving least squares approximation on the sphere, Mathematical Methods for Curves and Surfaces: Oslo 2000, Vanderbilt University, Nashville, TN, 2001
	Alyn P. Rockwood , Thomas W. Jensen, Two aspects of domain designing: C@@@@ curve rendering and blended map projections, ACM SIGGRAPH Computer Graphics, v.15 n.3, p.233-242, August 1981
	Hiroshi Akima, A Method of Bivariate Interpolation and Smooth Surface Fitting for Irregularly Distributed Data Points, ACM Transactions on Mathematical Software (TOMS), v.4 n.2, p.148-159, June 1978
	Azriel Rosenfeld, Progress in Picture Processing: 1969--71, ACM Computing Surveys (CSUR), v.5 n.2, p.81-108, June 1973
	Jean-Laurent Mallet, Discrete smooth interpolation, ACM Transactions on Graphics (TOG), v.8 n.2, p.121-144, April 1989
	A. Louise Perkins , Lucy F. Smedstad , Peter J. Sakalaukas, An explicit grid-independent interpolation algorithm, Proceedings of the 36th annual Southeast regional conference, p.108-110, April 1998
	Suzana Djurcilov , Alex Pang, Visualizing gridded datasets with large number of missing values (case study), Proceedings of the conference on Visualization '99: celebrating ten years, p.405-408, October 1999, San Francisco, California, United States
	Peter Litwinowicz , Lance Williams, Animating images with drawings, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.409-412, July 1994
	Robert J. Renka , Ron Brown, Algorithm 792: accuracy test of ACM algorithms for interpolation of scattered data in the plane, ACM Transactions on Mathematical Software (TOMS), v.25 n.1, p.78-94, March 1999
	Alain Fournier , William T. Reeves, A simple model of ocean waves, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.75-84, Aug. 1986
	Eyke Hüllermeier, Possibilistic instance-based learning, Artificial Intelligence, v.148 n.1-2, p.335-383, August 2003
	Domonkos Tikk , István Joó , László T. Kóczy , Péter Várlaki , Bernhard Moser , Tamás D. Gedeon, Stability of interpolative fuzzy KH controllers, Fuzzy Sets and Systems, v.125 n.1, p.105-119, January 2002
	Ken Museth , David E. Breen , Leonid Zhukov , Ross T. Whitaker, Level set segmentation from multiple non-uniform volume datasets, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
	Alan M. Lemon , Norman L. Jones, Building solid models from boreholes and user-defined cross-sections, Computers & Geosciences, v.29 n.5, p.547-555, June 2003
	Domonkos Tikk, Notes on the approximation rate of fuzzy KH interpolators, Fuzzy Sets and Systems, v.138 n.2, p.441-453, September 01, 2003
	Vinh Phu Nguyen , Timon Rabczuk , Stéphane Bordas , Marc Duflot, Review: Meshless methods: A review and computer implementation aspects, Mathematics and Computers in Simulation, v.79 n.3, p.763-813, December, 2008
	James R. Miller , Daniel C. Clibum , Johannes J. Feddema , Terry A. Slocum, Modeling and visualizing uncertainty in a global water balance model, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
	Odest Chadwicke Jenkins , Maja J. Mataric, Automated derivation of behavior vocabularies for autonomous humanoid motion, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia
	Yingcai Xiao , John P. Ziebarth , Chuck Woodbury , Eric Bayer , Bruce Rundell , Jeroen van der Zijp, The challenges of visualizing and modeling environmental data, Proceedings of the 7th conference on Visualization '96, p.413-ff., October 28-29, 1996, San Francisco, California, United States
	Carlos Zuppa, Good quality point sets and error estimates for moving least square approximations, Applied Numerical Mathematics, v.47 n.3-4, p.575-585, December 2003
	Detlef Ruprecht , Heinrich Müller, Image Warping with Scattered Data Interpolation, IEEE Computer Graphics and Applications, v.15 n.2, p.37-43, March 1995
	Christopher G. Atkeson , Andrew W. Moore , Stefan Schaal, Locally Weighted Learning, Artificial Intelligence Review, v.11 n.1-5, p.11-73, Feb. 1997
	Arpan Biswas , Vadim Shapiro , Igor Tsukanov, Heterogeneous material modeling with distance fields, Computer Aided Geometric Design, v.21 n.3, p.215-242, March 2004
	Lloyd A. Treinish, Case study: severe rainfall events in northwestern Peru (visualization of scattered meteorological data), Proceedings of the conference on Visualization '94, October 17-21, 1994, Washinton, D.C.
	Dror Aiger , Daniel Cohen-Or, Mosaicing Ultrasonic Volumes for Visual Simulation, IEEE Computer Graphics and Applications, v.20 n.2, p.53-61, March 2000
	Seungyong Lee , George Wolberg , Sung Yong Shin, Scattered Data Interpolation with Multilevel B-Splines, IEEE Transactions on Visualization and Computer Graphics, v.3 n.3, p.228-244, July 1997
	Dan Li , Jitender S. Deogun, Interpolation models for spatiotemporal association mining, Fundamenta Informaticae, v.59 n.2-3, p.153-172, February 2004
	Joachim Pouderoux , Jean-Christophe Gonzato , Ireneusz Tobor , Pascal Guitton, Adaptive hierarchical RBF interpolation for creating smooth digital elevation models, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA
	A. Iglesias, Computer graphics for water modeling and rendering: a survey, Future Generation Computer Systems, v.20 n.8, p.1355-1374, November 2004
	Dirk Langemann , Marcel Krüger, 3D Model of a droplet in an electric field, Mathematics and Computers in Simulation, v.66 n.6, p.539-549, 12 August 2004
	Damiana Lazzaro , Laura B. Montefusco, Radial basis functions for the multivariate interpolation of large scattered data sets, Journal of Computational and Applied Mathematics, v.140 n.1-2, p.521-536, 1 March 2002
	Augusto Sarti , Stefano Tubaro, Image-based surface modeling: a multi-resolution approach, Signal Processing, v.82 n.9, p.1215-1232, September 2002
	Lloyd A. Treinish, Visualization of Scattered Meteorological Data, IEEE Computer Graphics and Applications, v.15 n.4, p.20-26, July 1995
	Burkhard Wünsche , Ewan Tempero, A comparison and evaluation of interpolation methods for visualising discrete 2D survey data, Proceedings of the 2004 Australasian symposium on Information Visualisation, p.1-7, February 01, 2004, Christchurch, New Zealand
	Richard Tynan , David Marsh , Donal O'Kane , G. M. P. O'Hare, Intelligent agents for wireless sensor networks, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands
	Lixin Li , Peter Revesz, The relationship among GIS-oriented spatiotemporal databases, Proceedings of the 2003 annual national conference on Digital government research, p.1-4, May 18-21, 2003, Boston, MA
	Z. Zhang , C. Kleinstreuer, Airflow structures and nano-particle deposition in a human upper airway model, Journal of Computational Physics, v.198 n.1, p.178-210, 20 July 2004
	Carlos Zuppa, Error estimates for modified local Shepard's interpolation formula, Applied Numerical Mathematics, v.49 n.2, p.245-259, 1 May 2004
	S. Schaefer , T. Ju , J. Warren, A unified, integral construction for coordinates over closed curves, Computer Aided Geometric Design, v.24 n.8-9, p.481-493, November, 2007
	Ravikrishna Kolluri, Provably good moving least squares, ACM Transactions on Algorithms (TALG), v.4 n.2, p.1-25, May 2008
	K. Lipnikov , M. Shashkov , D. Svyatskiy , Yu. Vassilevski, Monotone finite volume schemes for diffusion equations on unstructured triangular and shape-regular polygonal meshes, Journal of Computational Physics, v.227 n.1, p.492-512, November, 2007
	Luke Jefferson , Richard Harvey, Accommodating color blind computer users, Proceedings of the 8th international ACM SIGACCESS conference on Computers and accessibility, October 23-25, 2006, Portland, Oregon, USA
	Scott Schaefer , Travis McPhail , Joe Warren, Image deformation using moving least squares, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
	Jun Gao , Peter Revesz, Voting prediction using new spatiotemporal interpolation methods, Proceedings of the 2006 international conference on Digital government research, May 21-24, 2006, San Diego, California
	Manjula A. Iyer , Layne T. Watson , Michael W. Berry, SHEPPACK: a Fortran 95 package for interpolation using the modified Shepard algorithm, Proceedings of the 44th annual southeast regional conference, March 10-12, 2006, Melbourne, Florida
	X. Y. Kou , S. T. Tan, Heterogeneous object modeling: A review, Computer-Aided Design, v.39 n.4, p.284-301, April, 2007
	Michael Macri , Suvranu De, An octree partition of unity method (OctPUM) with enrichments for multiscale modeling of heterogeneous media, Computers and Structures, v.86 n.7-8, p.780-795, April, 2008
	Erik Hubo , Tom Mertens , Tom Haber , Philippe Bekaert, Special Section: Point-Based Graphics: Self-similarity based compression of point set surfaces with application to ray tracing, Computers and Graphics, v.32 n.2, p.221-234, April, 2008
	Manjula A. Iyer , Layne T. Watson, A performance comparison of RIPPLE and LMS for high dimensional piecewise linear functions, Proceedings of the 45th annual southeast regional conference, March 23-24, 2007, Winston-Salem, North Carolina
	Yoh Shiraishi , Niwat Thepvilojanapong , Yosuke Tamura , Tatsuro Endo , Koichi Yamada , Nayuta Ishii , Hiroki Ishizuka , Keisuke Kanai , Yoshito Tobe, TomuDB: multi-resolution queries in heterogeneous sensor networks through overlay network, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia
	J. Göppert , W. Rosentiel, The Continuous Interpolating Self-organizing Map, Neural Processing Letters, v.5 n.3, p.185-192, June 1997
	Hui Xie , Kevin T. McDonnell , Hong Qin, Surface Reconstruction of Noisy and Defective Data Sets, Proceedings of the conference on Visualization '04, p.259-266, October 10-15, 2004
	Hui Xie , Jianning Wang , Jing Hua , Hong Qin , Arie Kaufman, Piecewise C1 Continuous Surface Reconstruction of Noisy Point Clouds via Local Implicit Quadric Regression, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.13, October 22-24, 2003
	Carlos H. C. Ribeiro, Embedding a Priori Knowledge in Reinforcement Learning, Journal of Intelligent and Robotic Systems, v.21 n.1, p.51-71, January 1998
	Camille Goudeseune, Interpolated mappings for musical instruments, Organised Sound, v.7 n.2, p.85-96, August 2002
	Paul Navratil , Jarrett Johnson , Volker Bromm, Visualization of Cosmological Particle-Based Datasets, IEEE Transactions on Visualization and Computer Graphics, v.13 n.6, p.1712-1718, November 2007
	Guangwei Yuan , Zhiqiang Sheng, Monotone finite volume schemes for diffusion equations on polygonal meshes, Journal of Computational Physics, v.227 n.12, p.6288-6312, June, 2008
	Alexander Belyaev, On transfinite barycentric coordinates, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
	Klaus Brügmann , Hannes Dohrn , Helmut Prendinger , Marc Stamminger , Mitsuru Ishizuka, Phase-based gesture motion parametrization and transitions for conversational agents with MPML3D, Proceedings of the 2nd international conference on INtelligent TEchnologies for interactive enterTAINment, January 08-10, 2008, Cancun, Mexico
	Barnabás Bede , Hajime Nobuhara , Martina Daňková , Antonio Di Nola, Approximation by pseudo-linear operators, Fuzzy Sets and Systems, v.159 n.7, p.804-820, April, 2008
	Enno Littmann , Helge Ritter, Learning and generalization in cascade network architectures, Neural Computation, v.8 n.7, p.1521-1539, October 1, 1996
	Jaakko Lehtinen , Matthias Zwicker , Emmanuel Turquin , Janne Kontkanen , Frédo Durand , François X. Sillion , Timo Aila, A meshless hierarchical representation for light transport, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
	Liqian Luo , Aman Kansal , Suman Nath , Feng Zhao, Sharing and exploring sensor streams over geocentric interfaces, Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, November 05-07, 2008, Irvine, California
	J. -D. Jang , V. Payan , A. A. Viau , A. Devost, The use of airborne lidar for orchard tree inventory, International Journal of Remote Sensing, v.29 n.6, p.1767-1780, March 2008
	Manjula A. Iyer , Morgan M. Harris , Layne T. Watson , Michael W. Berry, A performance comparison of piecewise linear estimation methods, Proceedings of the 2008 Spring simulation multiconference, April 14-17, 2008, Ottawa, Canada
	D. R. Palamara , M. Nicholson , P. Flentje , E. Baafi , G. M. Brassington, An evaluation of airborne laser scan data for coalmine subsidence mapping, International Journal of Remote Sensing, v.28 n.15, p.3181-3203, July 2007
	O. P. Sharma , H. C. Upadhyaya , A. Harzallah , R. Sadourny, Preparing area average rainfall on a regular grid from scattered raingauge data, Journal of Computational Methods in Sciences and Engineering, v.6 n.1-4, p.105-115, January 2006
	Manjula A. Iyer , Layne T. Watson , Jeffrey B. Birch, pRIPPLE: a parallel version of a polynomial-time piecewise linear estimation algorithm, Proceedings of the 2007 spring simulation multiconference, March 25-29, 2007, Norfolk, Virginia
	Jian Zhang , G. R. Liu , K. Y. Lam , Hua Li , G. Xu, A gradient smoothing method (GSM) based on strong form governing equation for adaptive analysis of solid mechanics problems, Finite Elements in Analysis and Design, v.44 n.15, p.889-909, November, 2008
	Tom Bobach , Gerald Farin , Dianne Hansford , Georg Umlauf, Natural neighbor extrapolation using ghost points, Computer-Aided Design, v.41 n.5, p.350-365, May, 2009
	Vincent Arsigny , Olivier Commowick , Nicholas Ayache , Xavier Pennec, A Fast and Log-Euclidean Polyaffine Framework for Locally Linear Registration, Journal of Mathematical Imaging and Vision, v.33 n.2, p.222-238, February 2009
	Jingyi Jin , Michael Garland , Edgar A. Ramos, MLS-based scalar fields over triangle meshes and their application in mesh processing, Proceedings of the 2009 symposium on Interactive 3D graphics and games, February 27-March 01, 2009, Boston, Massachusetts
	Nikolay Moshkin , Damrongsak Yambangwi, Steady viscous incompressible flow driven by a pressure difference in a planar T-junction channel, International Journal of Computational Fluid Dynamics, v.23 n.3, p.259-270, March 2009
	Haifeng Chen , Guofei Jiang, A gradient oriented recombination scheme for evolution strategies, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Shiaofen Fang , Ying Liu , Jeffrey Huang , Sophia Vinci-Booher , Bruce Anthony , Feng Zhou, Facial image classification of mouse embryos for the animal model study of fetal alcohol syndrome, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Alexander Kout , Heinrich Müller, Parameter optimization for spray coating, Advances in Engineering Software, v.40 n.10, p.1078-1086, October, 2009
	Xiaolin Li , Jialin Zhu, A Galerkin boundary node method and its convergence analysis, Journal of Computational and Applied Mathematics, v.230 n.1, p.314-328, August, 2009
	Samuel K. M. Chenoweth , Julio Soria , Andrew Ooi, A singularity-avoiding moving least squares scheme for two-dimensional unstructured meshes, Journal of Computational Physics, v.228 n.15, p.5592-5619, August, 2009
	David N. Cottingham , Robert K. Harle , Andy Hopper, Constructing accurate, space-efficient, wireless coverage maps for vehicular contexts, Proceedings of the 4th Annual International Conference on Wireless Internet, November 17-19, 2008, Maui, Hawaii
	Raanan Fattal, Edge-avoiding wavelets and their applications, ACM Transactions on Graphics (TOG), v.28 n.3, August 2009
	Brian Knight , Fei Ling Woon, Case base adaptation using solution-space metrics, Proceedings of the 18th international joint conference on Artificial intelligence, p.1347-1348, August 09-15, 2003, Acapulco, Mexico
	Sung W. Park , Lars Linsen , Oliver Kreylos , John D. Owens , Bernd Hamann, Discrete Sibson Interpolation, IEEE Transactions on Visualization and Computer Graphics, v.12 n.2, p.243-253, March 2006
	Dionissios T. Hristopulos , Samuel N. Elogne, Computationally efficient spatial interpolators based on spartan spatial random fields, IEEE Transactions on Signal Processing, v.57 n.9, p.3475-3487, September 2009
	Oren Goldshtein , Hagit Messer , Artem Zinevich, Rain rate estimation using measurements from commercial telecommunications links, IEEE Transactions on Signal Processing, v.57 n.4, p.1616-1625, April 2009

INDEX TERMS

General Terms:
Algorithms, Theory

Adobe Acrobat

QuickTime

Windows Media Player

Real Player