Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 10 of 11

Thread: 3d-Ellipsoid

Hybrid View

  1. #1
    Junior Member Regular Contributor
    Join Date
    Nov 2012
    Location
    Bremen, Germany
    Posts
    149

    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.
    Last edited by hlewin; 07-22-2013 at 05:52 AM.

  2. #2
    Member Regular Contributor
    Join Date
    Jun 2013
    Posts
    490
    Quote Originally Posted by hlewin View Post
    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.

    Quote Originally Posted by hlewin View Post
    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. #3
    Junior Member Regular Contributor
    Join Date
    Nov 2012
    Location
    Bremen, Germany
    Posts
    149
    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. #4
    Member Regular Contributor
    Join Date
    Jun 2013
    Posts
    490
    Quote Originally Posted by GClements View Post
    Note that in any of the case of an ellipsoid which touches three points
    Quote Originally Posted by hlewin View Post
    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.

    Quote Originally Posted by hlewin View Post
    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. #5
    Junior Member Regular Contributor
    Join Date
    Nov 2012
    Location
    Bremen, Germany
    Posts
    149
    Quote Originally Posted by GClements View Post
    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. #6
    Member Regular Contributor
    Join Date
    Jun 2013
    Posts
    490
    Quote Originally Posted by hlewin View Post
    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.


    Quote Originally Posted by hlewin View Post
    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.

    Quote Originally Posted by hlewin View Post
    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
  •