Algorithm for approximating convex bodies by a convex hull of ellipsoids
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