Fast tree-based redistancing for level set computations

Level set methods for moving interface problems require efficient technique s for transforming an interface to a globally defined function whose zero s et is the interface, such as the signed distance to the interface. This pap er presents efficient algorithms for this "redistancing" problem. The algor ithms use quadtrees and triangulation to compute global approximate signed distance functions. A quadtree mesh is built to resolve the interface and t he vertex distances are evaluated exactly with a robust search strategy to provide both continuous and discontinuous interpolants. Given a polygonal i nterface with N elements, our algorithms run in O (N) space and O(N log N) time. Two-dimensional numerical results show they are highly efficient in p ractice. (C) 1999 Academic Press.