Scalability of Delaunayn

As part of our work on a new model selection metric (Linear Reference Model (LRM) selection) we needed an idea of how Matlabs' triangulation routine (based on qhull) scales with the number of points and dimensionality.

The two plots below show the results of a simple test we did on a high end desktop machine. It turns out that the main limitation is memory usage, which in turn is very closely linked with the dimensionality. Beyond 6 dimensions with a couple thousand points we would just get a malloc memory error. For those cases we are looking at an iterative or approximate implementation. The Hull code by Clarkson also seems promising.






--Dirk