Multiresolution banded refinement to accelerate surface reconstruction from polygons

We propose a method for constructing a tiling between a pair of planar poly gons. Our technique uses multiresolution: tilings of lower resolution polyg ons are used to construct a tiling for the full resolution polygons. The ti lings are constructed using banned refinement, by restricted dynamic progra mming, in roughly linear time and space. By contrast, the optimal dynamic p rogramming method requires quadratic time and space. In our empirical study of surface reconstruction of brain contours our algorithm exhibited signif icant speedup over the optimal dynamic program, yet nearly always found an optimal reconstruction. Our approach appears to be generalizable to other g eometric problems solvable by dynamic programming, and flexible enough to b e tuned for varying data set characteristics. (C) 1999 Published by Elsevie r B.V. All rights reserved.