University of Georgia
Mathematics Department Colloquium
Nira Dyn
School of Mathematical Sciences, Tel Aviv University, Israel
Monday, February 16, 2004
Spline Subdivision Schemes for Compact Sets
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. We obtain an O(h^2) 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 an O(h) rate of approximation.
The results presented here were obtained in collaboration with E. Farkhi.