[vtkusers] optimized thin-plate-spline in VTK ?

[Khaldoun Zine El Abidine]

Hello everybody,

 

 

 

I am interested in an "optimized" Thin Plate Spline (TPS)
interpolation/smoothing algorithm (in 2D). It seems to me that VTK's
implementation uses the direct method (i.e. one that inverts a N*N
matrix). If that is the case, VTK's implementation has a O (N^2) memory
usage and a O (N^3) computational complexity, which is impractical for N
> 5000 when execution time requirements are strict (no more than a few
seconds on a regular PC). Algorithms in O (N log N) complexity exist in
the literature (see for example "Fast Solution Of The Radial Basis
Function Interpolation Equations: Domain Decomposition Methods, R. K.
BEATSON, W. A. LIGHT, AND S. BILLINGS, in Society for Industrial and
Applied Mathematics, Vol. 22, No. 5, pp. 1717-1740, 2000", among
others). Is anyone aware of a working implementation of this algorithm?
Is it, or will it be, available in present/future versions of VTK ?

 

 

Thank you in advance for you help.

 

 

 

Khaldoun.

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.vtk.org/pipermail/vtkusers/attachments/20031218/d867789c/attachment.htm>