Hierarchical Rbf

Hierarchical RBF interpolation has applications in the construction of shape models in 3D computer graphics (see Stanford Bunny image below), treatment of results from a 3D scanner, terrain reconstruction, and others.

This problem is informally named as "large scattered data point set interpolation."

The steps of the method (for example in 3D) consist of the following:

• Let the scattered points be presented as set ${\displaystyle \mathbf {P} =\{\mathbf {c} _{i}=(\mathbf {x} _{i},\mathbf {y} _{i},\mathbf {z} _{i})\vert _{i=1}^{N}\subset \mathbb {R} ^{3}\}}$
• Let there exist a set of values of some function in scattered points ${\displaystyle \mathbf {H} =\{\mathbf {h} _{i}\vert _{i=1}^{N}\subset \mathbb {R} \}}$
• Find a function ${\displaystyle \mathbf {f} (\mathbf {x} )}$ that will meet the condition ${\displaystyle \mathbf {f} (\mathbf {x} )=1}$ for points lying on the shape and ${\displaystyle \mathbf {f} (\mathbf {x} )\neq 1}$ for points not lying on the shape
• As J. C. Carr et al. showed, this function looks like ${\displaystyle \mathbf {f} (\mathbf {x} )=\sum _{i=1}^{N}\lambda _{i}\varphi (\mathbf {x} ,\mathbf {c} _{i})}$ where:

${\displaystyle \varphi }$ — is RBF; ${\displaystyle \lambda }$ — is coefficients that are the solution of the system shown in the picture:

For determination of surface, it is necessary to estimate the value of function ${\displaystyle \mathbf {f} (\mathbf {x} )}$ in interesting points x. A lack of such method is a considerable complication ${\displaystyle \mathbf {O} (\mathbf {n} ^{2})}$ to calculate RBF, solve system, and determine surface.

• Reduce interpolation centers (${\displaystyle \mathbf {O} (\mathbf {n} ^{2})}$  to calculate RBF and solve system, ${\displaystyle \mathbf {O} (\mathbf {m} \mathbf {n} )}$  to determine surface)
• Compactly support RBF (${\displaystyle \mathbf {O} (\mathbf {n} \log {\mathbf {n} })}$  to calculate RBF, ${\displaystyle \mathbf {O} (\mathbf {n} ^{1.2..1.5})}$  to solve system, ${\displaystyle \mathbf {O} (\mathbf {m} \log {\mathbf {n} })}$  to determine surface)
• FMM (${\displaystyle \mathbf {O} (\mathbf {n} ^{2})}$  to calculate RBF, ${\displaystyle \mathbf {O} (\mathbf {n} \log {\mathbf {n} })}$  to solve system, ${\displaystyle \mathbf {O} (\mathbf {m} +\mathbf {n} \log {\mathbf {n} })}$  to determine surface)

An idea of hierarchical algorithm is an acceleration of calculations due to decomposition of intricate problems on the great number of simple (see picture).  

In this case, hierarchical division of space contains points on elementary parts, and the system of small dimension solves for each. The calculation of surface in this case is taken to the hierarchical (on the basis of tree-structure) calculation of interpolant. A method for a 2D case is offered by Pouderoux J. et al. For a 3D case, a method is used in the tasks of 3D graphics by W. Qiang et al. and modified by Babkov V.