This <math>O(n^3)</math> time complexity was eliminated in the approximate "sparse field" level set method introduced by Whitaker in 1998.<ref name=Whitaker>Whitaker, R. T. 1998. "A level-set approach to 3d reconstruction from range data." ''[[International Journal of Computer Vision]].'' 29(3)203–231.</ref> The sparse field level set method employs a set of linked lists to track the active voxels around the interface. This allows incremental extension of the active region as needed without incurring any significant overhead. While consistently <math>O(n^2)</math> efficient in time, <math>O(n^3)</math> storage space is still required by the sparse field level set method. See<ref name=Lankton>S. Lankton. "Sparse Field Method - Technical Report." April 21, 2009 <http://www.shawnlankton.com/2009/04/sfm-and-active-contours/></ref> for implementation details.
===Sparse block grid===
Line 18:
===Octree===
The [[octree]] level set method, introduced by Strain in 1999<ref name=Strain>Strain, J. 1999. "Tree methods for moving interfaces." ''[[Journal of Computational Physics]]''. 151(2)616–648.</ref> and refined by Losasso, Gibou and Fedkiw,<ref name=Losasso>Losasso, F., Gibou, F., & Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. [[ACM Transactions on Graphics]]. 23(3)457–462.</ref> and more recently by Min and Gibou<ref name=MinGibou>Min, C. & Gibou, F. 2007. A second order accurate level set method on non-graded adaptive cartesian grids. [[Journal of Computational Physics]]. 225(1)300–321.</ref> uses a tree of nested cubes of which the leaf nodes contain signed distance values. Octree level sets currently require uniform refinement along the interface (i.e. the narrow band) in order to obtain sufficient precision. This representation is efficient in terms of storage, <math>O(n^2),</math> and relatively efficient in terms of access queries, <math>O(\log\, n).</math> An advantage of the level method on octree data structures is that one can solve the partial differential equations associated with typical free boundary problems that use the level set method. The CASL research group<ref name=CASL>http://www1.engr.ucsb.edu/~fgibou/Research.html</ref> has developed this line of work in computational materials, computational fluid dynamics, electrokinetics, image guided surgery and controls.
