# The Industry's Foundation for High Performance Graphics

1. ## 3d-Ellipsoid

I have some questions more of curiosity.
I wouldn't seriously mind if no one could answer them:

1. Given a set of points - is there a simple way to construct/compute the ellipsoid with the lowest volume given by
X2/W2 + Y2/H2 + Z2/D2 - 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?

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?

I did some googling but didn't find the right things and as I don't think those questions are too easy to answer I decided to simply draw the ellipsoid by eye. Nontheless I would like to hear oppinions. Does someone know a good book dealing with geometric problems of this kind? I tried to construct an ellipsoid through three points by simply substituting in the equation but this didn't get really far.

2. Originally Posted by hlewin
1. Given a set of points - is there a simple way to construct/compute the ellipsoid with the lowest volume given by
X2/W2 + Y2/H2 + Z2/D2 - 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?
Here's one way to look at this.

First, make the substitutions:
P = 1/W2
Q = 1/H2
R = 1/D2

Thus, a point <x,y,z> is inside the ellipsoid if
X2P + Y2Q + Z2R <= 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.

Originally Posted by hlewin
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?
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.

3. The vertices, edges and faces of this polyhedron can be found using the simplex method.
Thank you! I didn't think about it as at the time I asked myself the question I was already finished with the problem despite having heard of the method. The GNU-Scientific Library seems to have an implementation of a simplex-minimizer.

Note that in any of the case of an ellipsoid which touches three Points
I'm afraid I don't understand. In my understanding each point on the surface of the polyhedron is a valid solution but I do not see how this would mean that it necessarily touches more than one point of the set. Anyways: the question was meant in a much simpler way: How many random surface-points does one need to uniquely identify an ellipsoid? My Initial guess was three, but that only seems to work for special points.
EDIT: The tought was to simply take the bounding-box around the point set and make an ellipsoid from it as I do not really need a perfectly minimized ellipsoid, but this produces a set of them.

4. Originally Posted by GClements
Note that in any of the case of an ellipsoid which touches three points
Originally Posted by hlewin
I'm afraid I don't understand. In my understanding each point on the surface of the polyhedron is a valid solution but I do not see how this would mean that it necessarily touches more than one point of the set.
Sorry, the "any" shouldn't have been there. It should have said:
Note that in of the case of an ellipsoid which touches three points
Such cases correspond to a vertex of the polyhedron. Edges correspond to ellipsoids which touch two points, faces to ellipsoids which touch one point, and the interior to ellipsoids which contain all points but touch none.

Originally Posted by hlewin
Anyways: the question was meant in a much simpler way: How many random surface-points does one need to uniquely identify an ellipsoid? My Initial guess was three, but that only seems to work for special points.
In general, three. It's just a case of three equations in three unknowns.

But the actual requirement is for three linearly-independent equations. There are cases where multiple points specify the same equation, making some of them redundant.

As (-X)2=X2 etc, the ellipsoid is symmetric about the X, Y and Z planes. So if the point (x,y,z) lies on the surface of the ellipse, then so do the other seven points obtained by reflecting the original point in the X, Y and Z planes, i.e. (-x,y,z), (-x,-y,-z) and so on.

More generally, if the square of one point (X2,Y2,Z2) is a linear combination of the squares of the other two, then you don't have three linearly-independent equations and the ellipsoid isn't uniquely defined. The symmetry issue is just a specific case of this.

Another specific case is when one point differs from another by a scale factor (i.e. the point lies on a line segment between another point and the origin). As a consequence, there is no upper bound on the number of points required. If you had an infinite number of points forming a line segment with one end at the origin, it would be as if you only had one point (the line segment's other endpoint).

5. Originally Posted by GClements
Such cases correspond to a vertex of the polyhedron. Edges correspond to ellipsoids which touch two points, faces to ellipsoids which touch one point, and the interior to ellipsoids which contain all points but touch none.
Is this an observation or derived from the algorithm? I read the sentence, that the optimal solution corresponds to a vertex of the polyhedron, but imagining an ellipse and a point that is outside of it
Code :
``` /\.
/  \
\  /
\/```

the point can be made to lie on the surface of the ellipse by increasing it's width OR height. So I do not see how an optimal solution would require to hit more than one point of the set (and even that is something I can just derive from imagination without having proven it - sorry if I don't get the point).

6. Originally Posted by hlewin
Is this an observation or derived from the algorithm?
It's an observation on the nature of <P,Q,R> space and the polyhedron.

• A point (in <P,Q,R> space) corresponds to an ellipsoid (in <x,y,z> space).
• A plane corresponds to the set of ellipsoids which touch a specific point.
• A (linear) half-space corresponds to the set of ellipsoids which contain (incl. touch) a specific point.
• The filled polyhedron corresponds to the set of ellipsoids which contain all points.
• The surface of the polyhedron corresponds to the set of ellipsoids which contain all points and touch at least one point.
• The interior of the polyhedron corresponds to the set of ellipsoids which contain all points and touch none of them.
• Each face corresponds to the set of ellipsoids which touch a specific point and contain all points.
• Each edge corresponds to the set of ellipsoids which touch two specific points and contain all points.
• Each vertex corresponds to the set of ellipsoids which touch three specific points and contain all points.

Originally Posted by hlewin
I read the sentence, that the optimal solution corresponds to a vertex of the polyhedron,
An optimal solution corresponds to a point on the surface of the polyhedron, not necessarily a vertex.

Because the function being maximised is non-linear (P*Q*R), it's possible for the value at a point within a face to be greater than that at any of its vertices. This is why the simplex method cannot be used to find the optimal solution directly. It can only be used to enumerate the space of candidate solutions; non-linear methods must be used to find the global maximum.

Originally Posted by hlewin
the point can be made to lie on the surface of the ellipse by increasing it's width OR height. So I do not see how an optimal solution would require to hit more than one point of the set (and even that is something I can just derive from imagination without having proven it - sorry if I don't get the point).
An optimal solution doesn't require it to hit more than one point.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•