A divide-and-conquer algorithm for grid generation (Q1330487)

The algorithm proposed here generates grid points in plane domains with four smooth boundary curves. It is similar to what one does instinctively when asked to generate a grid when given only the boundary: an algorithm starts with the initial boundary curves and fills in the interior grids, one curve at a time. At each stage, the new grid curve most reduces the distance between the existing grid curves, that is, we add a grid curve that is farthest from the existing grid curves. (E.g., for an annulus or a similar region, this strategy causes several radial curves to be generated before any curves in the other direction are generated.) Many of the heuristic decisions made in designing the algorithm were chosen to mimic the instinctive process. To add a grid curve, a shape- preserving and monotonicity-preserving parametric cubic Hermite interpolant, due to the authors and \textit{A. S. Edelman} [Math. Comput. 52, No. 186, 471-494 (1989; Zbl 0693.41004)] through the known points is defined. (The monotonicity preservation insures that between the existing knots the interpolant preserves the sign of the tangent at the knots. The interpolation is used both for generating the new tangent vectors and for producing the grid points on the new curve.) The grid generated here is fit for moderately distorted regions and can be used directly. When rough areas or singularities caused by the grid curves crossing occur in extreme cases, the rezoning techniques of \textit{W. D. Henshaw} and the second author [Static rezone methods on logically rectangular grids, Los Alamos National Lab. Rep. (1986)] smoothes the grid, improves its orthogonality or its resolution of a given equation.