Natural Neighbor Concepts in Scattered Data Interpolation and Discrete Function Approximation

Abstract: The concept of natural neighbors employs the notion of distance to define local neighborhoods in discrete data. Especially when querying and accessing large scale data, it is important to limit the amount of data that has to be processed for an answer. Because of its implicit definition on distances, the natural neighbor concept is extremely well suited to provide meaningful neighborhoods in spatial data with a scattered, inhomogeneous distribution. This paper revisits some unique properties of natural neighbor based methods and summarizes important findings for their successful application to scattered data inter-polation, and the computation of discrete harmonic functions.