[SciPy-Dev] N-dimensional interpolation

[Pauli Virtanen]

Sun, 25 Jul 2010 10:45:23 -0600, Charles R Harris wrote:
> Do you mean scipy.interpolate?

Yep.

[clip]
> I'm not a computational geometry expert, but I expect the 2-D
> performance or scikits.delaunay takes advantage of a special algorithm
> for that case (I recall googling for that back when). Perhaps it can be
> adapted to the higher dimension case or adapted for searching. Just
> random thoughts here, I have no actual experience with these sorts of
> problems.

Optimizing the time spent in Qhull is probably very difficult, so I think 
we'll just have to live with that part.

As far as I understand, the search algorithm in scikits.delaunay walks 
the triangles by hopping to a neighbour chosen so that the target point 
is on positive side of the corresponding ridge. That generalizes to N-D 
easily.

Randomizing the interpolation points causes a 20x hit on the current 
search algorithm, whereas scikits.delaunay gets away with a 4x 
performance drop with the same input, so there could be some room for 
improvement here.

-- 
Pauli Virtanen