# 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