Spline Subdivision Schemes for Compact Sets

Tuesday, April 24, 2001 - 9:30am - 10:30am
Keller 3-180
Nira Dyn (Tel Aviv University)
Motivated by the problem of the reconstruction of 3D objects from their 2D cross sections, we consider spline subdivision schemes operating on data consisting of compact sets. A spline subdivision scheme generates from such initial data a sequence of set-valued functions, with compact sets as images, which converges to a limit set-valued function. In the case of 2D sets, the limit set valued function, with 2D sets as images, describes a 3D object.

For the case of data consisting of convex sets, we replace addition by Minkowski sums of sets. Then the spline subdivision schemes generate limit set-valued functions which can be expressed as linear combinations of integer shifts of a B-spline, with the initial sets as coefficients. The subdivision techniques are used to conclude that these limit set-valued spline functions have shape preserving properties similar to those of scalar spline functions. We obtain O(h2) rate of approximation by the limit function, under mild smoothness assumptions on the set-valued function, from which the initial data is sampled.

For the case of non-convex sets we show that the limit of the spline subdivision schemes, using the Minkowski sums, is too large to be a good approximation.

To define spline subdivision schemes for general compact sets, we use the representation of spline subdivision schemes in terms of repeated averages, and replace the usual average by a binary operation between two compact sets, termed the metric average. These schemes are shown to converge in the Hausdorff metric, and provide O(h) rate of approximation.

The results presented here, were obtained in collaboration with E. Farkhi.