Phil L. Bowers, William E. Dietz and Stephen L. Keeling

This work is motivated by the need to pass information efficiently among subdomains when solving partial differential equations with a domain decomposition approach. Because of ever greater demands for flexibility, no restrictive assumptions are made about the grids used to discretize the subdomains. Indeed, the union of all grid field points is treated as a general collection of points from which information must be interpolated onto a much smaller set of subdomain boundary points. A natural method of interpolation for a given boundary point involves identifying nearby field points as vertices of an encompassing Delaunay simplex, i.e., a simplex containing the boundary point while its circumsphere contains no field points. Accordingly, this paper presents methods for rapidly extracting these required interpolation elements from a Delaunay tesselation of field points without first constructing a much more costly global tesselation for the entire point set. The methods developed and analyzed have been termed the "Shrink Wrap" and "Oozing Bubble" methods. Proofs of convergence are provided for both methods. An example application from computational fluid dynamics is presented to demonstrate the use of these methods for hybrid computational grid systems.