Deleting points from convex hull in n-dimensions

Question

I want to delete the vertex from a convex hull in n-dimensions that least/most reduces some hull attribute, such as area or volume. This can be done brute force by deleting a vertex, computing a new hull and an area/volume with one fewer vertex (using for example scipy.ConvexHull or qHull), then repeating for each vertex.

I suspect there is a way to make this more efficient by using a Delaunay triangulation, reusing almost all of that triangulation going from one vertex to the next. Three related questions: (1) how are the triangulation and hull related in n-dimensions; (2) can I compute hull volume and area from the triangulation; and (3) can a new triangulation be constructed from the old, with one hull vertex deleted?

Answer 1

how are the triangulation and hull related in n-dimensions

In 2D, the triangulation that fills the whole convex hull is composed by triangles. The hull itself is built with segments. In 3D the elements are tetrahedra and triangles. In n-D, I can't imagine, let's say you have nD elements.

The point in a Delaunay triangulation is that no point lies inside the n-sphere defined by any other n points. This "inside test" can be calculated with a n+1 determinant.

can I compute hull volume and area from the triangulation

Yes. Just sum the length/area/volume of all elements.

To compute the area of a 3D hull, you can select those tetrahedra that have a not-shared face. Those not-shared faces form the 3D hull.

can a new triangulation be constructed from the old, with one hull vertex deleted?

Yes. For example, in 2D, if a vertex is deleted then all triangles sharing that vertex must be deleted too. Then only the resulting interior hole must be recomputed.

I don't know if there's some typical software able to do all of above. But it's not difficult to code yourself triangulator, albeit it requires quite attention.

Answer 2

My thanks to Ripl2. Those comments got me started. I want to elaborate a bit on the process outlined there for filling in a hole after a point is deleted from a Delaunay triangulation in n dimensions. This applies to any such deletion, not only to a deletion of a point on the convex hull.

A simplex in n dimensions has n+1 vertices. A circumsphere can always be fit to the vertices. The defining property of a simplex in the triangulation is that the interior of its circumsphere is empty of points in the data.

When a point is removed, all simplices, facets, and circumspheres involving the point are also removed. To fill the hole, all points with which the removed point previously shared a circumsphere (or equivalently, a simplex) in the triangulation must be handled. Let S be the set of such points.

For each subset Q of S containing n+1 points, compute the circumsphere. If the circumsphere contains no points of S-Q, the Q simplex is part of the revised triangulation; otherwise, it is rejected.