# 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? – Jeffε Jul 4 '12 at 17:44
• yes I mean the convex hull – docBrown Jul 4 '12 at 18:53
• Edited for clarity (I hope). – Jeffε Jul 4 '12 at 20:42

## 1 Answer

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