algorithm for triangular surface elements enclosing random 3D points

Question

Suppose 3d space has certain number of random points. All these points can be enclosed on a surface made up of triangular elements such that vertices of these triangles are the random points with the condition that surface area gets maximised . I'm interested in finding the volume enclosed by this whole surface (i.e. of polyhedra).

Quickhull algorithm finds the convex body around these points. In this case, some concave part of the surface needs to be accounted such that the min volume enclosing all the random points is obtained. There are some known algorithms which give volume for such polyhedras provided the points forming each of the outer triangular elements are given.

I am looking for some algorithm which provides the outermost triangular elements. Eventual computer code will be written based on this algorithm.

PS: modified to include condition on surface area

Answer 1

What you are asking is far from clear. Here is an attempt to clarify things. At present, I don't understand how you cannot define such a surface with triangular facets in a unique way.

Let us take the example below which is the 2D equivalent of your 3D issue : consider the 6 vertices of a hexagon + point $M$ which is somewhere inside their convex hull : you see depicted two ways to include $M$ in a 7-sided polygon (red and dotted blue) and they have different areas (but maybe you want to select the one that has minimal area/surface ?)

Replace "line segments" and "areas" by "triangles" and "volumes" resp. and you will be convinced - so I think - that your issue has no unique answer and that you must add other constraints. But maybe, here, I have misunderstood what you call "outermost" elements ?

Answer 2

Delaunay triangulations can be built in 3D using tetrahedra. Those tetrahedra that have a face not shared with other tetrahedra form the outer surface.

Delaunay triangulations generate a convex surface. If you want another type you may search for "marching cubes" e.g. this link, which needs to know in advance which points form the surface. Or "Ball Pivoting", which works well when all vertices are quite homogeneously distributed in the surface (affects the radious of the ball).

There's another algorithm, search for "Segment Maxima". This works by searching farthest points inside small cones (that fill the whole sphere), and then doing a 2D triangulation with these points.