[QUOTE=hlewin;1252881]1. Given a set of points - is there a simple way to construct/compute the ellipsoid with the lowest volume given by

`X`

2/`W`

2 + `Y`

2/`H`

2 + `Z`

2/`D`

2 - 1 = 0

that encompasses all points? How about the ellipsoids that have at least one of it’s axis-lengths minimized? Does one imply the other?[/QUOTE]

Here’s one way to look at this.

First, make the substitutions:

`P`

= 1/`W`

2

`Q`

= 1/`H`

2

`R`

= 1/`D`

2

Thus, a point <x,y,z> is inside the ellipsoid if

`X`

2`P`

+ `Y`

2`Q`

+ `Z`

2`R`

<= 1

This forms a linear half-space in <P,Q,R> space.

The set of ellipsoids which contain all points is thus a convex polyhedron in <P,Q,R> space defined as the intersection of a set of half-spaces, each defined by one of the points.

The vertices, edges and faces of this polyhedron can be found using the simplex method. If you wanted the ellipsoid which minimised a linear function in P, Q, and R, that could also be found by the simplex method.

However, in this case, you’re trying to minimise W*H*D = 1/sqrt(P*Q*R), so you’re trying to maximise P*Q*R.

The optimum value will lie on the surface of the polyhedron, but as the function isn’t linear, it won’t necessarily be a vertex. Having enumerated the vertices, edges and faces, you need to find the value of P*Q*R for each vertex, and its maximum value for each edge and face.

[QUOTE=hlewin;1252881]

2. How many distinct points (`X`

,`Y`

,`Z`

) on the surface of such a 3d-ellipsoid are needed to reduce the number of possible solutions to the ellipsoid-equation to one assuming that the points are chosen at random?[/QUOTE]

I’m not sure I understand the question.

In the above approach, each vertex of the polyhedron correspond to an ellipsoid which touches three points… Similarly, each edge corresponds to a one-dimensional family of ellipsoids which touch the same two points (and possibly others), while each face corresponds to a two-dimensional family of ellipsoids which touch a specific point.

Note that in any of the case of an ellipsoid which touches three points, it may coincidentally touch additional points. In this situation, the simplex method will produce multiple vertices which are coincident but structurally distinct, resulting in some degenerate (zero length or area) edges and faces.