> Now suppose you have a set of vectors in a 6-D space. The
> convex hull would be a 5-D surface. What is the algorithm
> to determine this surface, for such a set? What is its complexity?
Quickhull can be extended to any number of dimensions. It's O(n.log(n))
average-case, O(n^2) worst-case, where n is the number of points.
Briefly: for an N-dimensional space, find the points with the minimum and
maximum values in each dimension, i.e. those lying on the axis-aligned
bounding hypercuboid. These points must be vertices of the convex hull.
From these, choose N points to define a hyperplane. On each side, find the
point farthest from the plane. Along with the original N points, this
forms an N-dimensional simplex (triangle, tetrahedron, etc) having N+1
vertices.
Any points inside the simplex cannot be vertices of the convex hull
and are eliminated from future searches. For each face of the simplex
(other than that formed by the initial plane), repeat the process until no
points lie outside.
The wikipedia page for Quickhull has an animation for the 2D case.
> Or, given a proposed surface, as the union of linear surfaces
> in n dimensions, how to determine if it constitutes the convex
> hull for some n+1 dimensional space? Then, given a point in
> that (n+1)-D space, how to determine if it lies within the volume
> enclosed by that convex hull?
Any convex polytope is the intersection of a set of linear half-spaces,
each defined by a linear inequality c1.x1+c2.x2+... <= k. The surface
is defined by convex polygons embedded in the corresponding hyperplanes
c1.x1+c2.x2+... = k. The distance of the point <x1,x2,...> to the
plane is (c1.x1+c2.x2+...-k)/sqrt(c1^2+c2^2+...).
A point is inside the polytope if and only if it is inside all of the
half-spaces, i.e. all of the inequalities hold.
Reply by RichD●March 24, 20152015-03-24
Convex sets have become important in numerical optimization,
so I'm trying to edjicate myself.
Given some subset of points in a vector space, one must first
determine its convex hull. For a set of points on a plane, this
is easy to visualize However, I don't see how to write the code
to accomplish this.
Now suppose you have a set of vectors in a 6-D space. The
convex hull would be a 5-D surface. What is the algorithm
to determine this surface, for such a set? What is its complexity?
Or, given a proposed surface, as the union of linear surfaces
in n dimensions, how to determine if it constitutes the convex
hull for some n+1 dimensional space? Then, given a point in
that (n+1)-D space, how to determine if it lies within the volume
enclosed by that convex hull?
--
Rich