questions on convex hull

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

On Tue, 24 Mar 2015 14:07:54 -0700, RichD wrote:

> 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.