<p>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.</p>

<p>The associated papers can be found here:</p>

<p><a href="http://www.cs.ucdavis.edu/~amenta/pubs/crust.pdf" rel="nofollow">A New Voronoi-Based Surface Reconstruction Algorithm</a></p>

<p><a href="http://www.cs.ucdavis.edu/~amenta/pubs/sm.pdf" rel="nofollow">The Power Crust</a></p>

<p><a href="http://www.cs.ucdavis.edu/~amenta/pubs/powerTheory.pdf" rel="nofollow">The Power Crust, Unions of Balls, and the Medial Axis Transform</a></p>

CC BY-SA 3.0
2012-07-10T01:10:51.703Z
2012-07-10T01:10:51.703Z
Jason
<p>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.</p>

<p>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. </p>

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

CC BY-SA 3.0
2012-07-04T17:44:54.703Z
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ε
CC BY-SA 3.0
2012-07-04T18:53:44.747Z
yes I mean the convex hull
docBrown
CC BY-SA 3.0
2012-07-04T20:42:39.633Z
Edited for clarity (I hope).
Jeffε
<cg.comp-geom><approximation><convex-geometry>
Algorithm for approximating convex bodies by a convex hull of ellipsoids
docBrown
# Algorithm for approximating convex bodies by a convex hull of ellipsoids

(Asked by: username_0 on 2012-07-04)

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.

**Tags:** cg.comp-geom, approximation, convex-geometry
> **Comments:**
> **username_1**: 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?  
> **username_0**: yes I mean the convex hull  
> **username_1**: Edited for clarity (I hope).  

---

## 1 answers

### Answer by username_2 on 2012-07-10. Score: 1

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](http://www.cs.ucdavis.edu/~amenta/pubs/crust.pdf)

[The Power Crust](http://www.cs.ucdavis.edu/~amenta/pubs/sm.pdf)

[The Power Crust, Unions of Balls, and the Medial Axis Transform](http://www.cs.ucdavis.edu/~amenta/pubs/powerTheory.pdf)


---

