<html>
<head>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 10 (filtered)">
<style>
<!--
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman";}
h3
{margin-top:12.0pt;
margin-right:0cm;
margin-bottom:3.0pt;
margin-left:61.2pt;
text-indent:-25.2pt;
page-break-after:avoid;
font-size:13.0pt;
font-family:Arial;}
a:link, span.MsoHyperlink
{color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{color:purple;
text-decoration:underline;}
p.MsoAutoSig, li.MsoAutoSig, div.MsoAutoSig
{margin-right:0cm;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman";}
span.EmailStyle17
{font-family:Arial;
color:windowtext;}
@page Section1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.Section1
{page:Section1;}
/* List Definitions */
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
-->
</style>
</head>
<body lang=EN-US link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><font size=2 face=Arial><span lang=FR-CA style='font-size:
10.0pt;font-family:Arial'> </span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Hello everybody,</span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'> </span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'> </span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'> </span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>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 ?</span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'> </span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'> </span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Thank you in advance for you help.</span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'> </span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'> </span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'> </span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span lang=FR-CA style='font-size:
10.0pt;font-family:Arial'>Khaldoun</span></font><font size=2 face=Arial><span
lang=FR-CA style='font-size:10.0pt;font-family:Arial'>.</span></font></p>
<p class=MsoAutoSig style='margin:0cm;margin-bottom:.0001pt'><font size=3
face="Times New Roman"><span style='font-size:12.0pt'> </span></font></p>
</div>
</body>
</html>