Tree methods for moving interfaces

Fast adaptive numerical methods for solving moving interface problems are presented. The methods combine a level set approach with frequent redistancing and semi-Lagrangian time stepping schemes which are explicit yet unconditionally stable. A quadtree mesh is used to concentrate computational effort on the interface, so the methods move an interface with N degrees of freedom in O(N log N) work per time step. Efficiency is increased by taking large time steps even for parabolic curvature flows. The methods compute accurate viscosity solutions to a wide variety of difficult moving interface problems involving merging, anisotropy, faceting, and curvature. (C) 1999 Academic Press.