What is Known About the Complexity of Calculating Minimal Surface Polyhedra? I am currently ruminating about ways of generalizing Minimum Spanning Trees to Minimum Spanning "Hypertrees", where the cost is associated with simplex volumes and, where certain topological constraints must be met (the "Hyper" is borrowed from the use in  Hyper Graphs);
I also managed to devise a Binary Programming formulation, which could also be adapted for calculating Minimal Surface Area Polyhedra spanning a set of 3D points, but I couldn't find anything new on the complexity of that task; there is a paper by Joseph O'Rourke from 1981 (Polyhedra of minimal area as 3D object models), where it is stated, that it is not known whether it is an NP problem.  

Question:
  have there been improvements in determining the computational complexity of finding polyhedra of minimal surface area through a given set of 3D points?  

 A: The problem is NP-hard even for the restricted version when the points form contours
lying in parallel planes:

Althaus, Ernst, and Christian Fink. "A polyhedral approach to surface reconstruction from planar contours." Integer Programming and Combinatorial Optimization. Springer Berlin Heidelberg, 2002. 258-272. 
  (download link for conf version).

Here is an illustration of a part of their proof:

 


Perhaps also of interest is that there may not exist a polyhedron through given points,
i.e., vertices might need be added:


Carole Gitlin, Joseph O'Rourke, and Vinita Subramanian. "On reconstructing polyhedra from parallel slices." International Journal of Computational Geometry & Applications 6.01 (1996): 103-122. (link to paper download)

 
 
 
 
 
 
 
 
 


Work on discrete minimal surfaces might be relevant to your
interests, e.g.,

Polthier, Konrad. "Computational aspects of discrete minimal surfaces." Proc. of the Clay Summer School on Global Theory of Minimal Surfaces, 2002. (link to Konrad's papers).

