# Algorithm for approximating convex bodies by a convex hull of ellipsoids

I am working in the field of structural engineering and I would like to find an efficient algorithm to construct an approximation (in the Hausdorff metric) of a convex body $K$ by the convex hull of $n$ ellipsoids, for some fixed $n$. Currently I am only working in dimensions 2 and 3.

My first idea was to work in the dual space using the support function $h_K$ of $K$, which I can compute for a sample of $M$ points on the unit sphere $S_d$, and to minimize the discrete error between $h_K$ and the support function of the approximating set in the $l^{\infty}$-norm.

Does anybody have another idea or some references to give me? I was unable to find any related work on this subject.

• What is "the convex union of ellipsoids"? The union of two ellipsoids is convex if and only if one is contained in the other. Do you mean the convex hull? Commented Jul 4, 2012 at 17:44
• yes I mean the convex hull Commented Jul 4, 2012 at 18:53
• Edited for clarity (I hope). Commented Jul 4, 2012 at 20:42

You may want to look into the "Crust" and "Power Crust" algorithms from Amenta, et al. Rather than ellipsoids, it uses spheres, but I believe the concept is simliar as they are able to, at the limit, construct a water-tight body from an unorganized point-cloud. In their case the desire was to mesh the original intended shape from the medial axis created between the delaunay and voroni spaces of the point-cloud rather than a convex hull of the points, but you may be able to glean some interesting ideas.

The associated papers can be found here:

A New Voronoi-Based Surface Reconstruction Algorithm

The Power Crust

The Power Crust, Unions of Balls, and the Medial Axis Transform