Matlab algorithm for point location in Delaunay triangulations (tsearchn)

Does anyone know which algorithm Matlab uses for point location in a Delaunay triangulation (function 'tsearchn')? I haven't been able to google it. I wonder if it's just brute force, or some sophisticated method.

The interest is purely theoretical, I want to compare performance of different point location approaches in high-dimensional triangulations and need a baseline for comparison.

A paper reference would be very welcome, or at least a general idea of the algorithm and its complexity in terms of d (dimension) and n (number of points/simpleces). If this, however, cannot be disclosed, than so be it.

Answer 1

[Keith Dalbey]

A few years back I talked to the guy who wrote qhull and he said the "optimally fast" way to identify the triangles that contained the points would be to modify the qhull algorithm to use two sets of points at the same time (and I'm paraphrasing from memory here), as it inserts planes into the first set, keep track of what sides of the planes that the second set of points were located in. So the complexity of the optimal approach should be the complexity of qhull. I had also asked this question (how their new tsearchn algorithm worked, when the time for a particular problem I was working on dropped from several minutes to a few seconds) of mathworks and the non-descriptive answer I got was that it was based on qhull and that the specifics of the algorithm were proprietary, but I'd guess their using the "optimal" qhull approach.