Fast tree-based redistancing for level set computations

Level set methods for moving interface problems require efficient techniques for transforming an interface to a globally defined function whose zero set is the interface, such as the signed distance to the interface. This paper presents efficient algorithms for this "redistancing" problem. The algorithms use quadtrees and triangulation to compute global approximate signed distance functions. A quadtree mesh is built to resolve the interface and the vertex distances are evaluated exactly with a robust search strategy to provide both continuous and discontinuous interpolants. Given a polygonal interface 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 practice. (C) 1999 Academic Press.