Let $e$ and $d$ be real numbers such that $0 < e < d$. Are there known functions $B(e,d)$ that are upper bounds (close to or even equal to least upper bounds) for the surface area of the boundaries of (not necessarily convex) polyhedra in $E^3$ which have a diameter not greater than $d$ and every distinct pair of whose vertices have a distance apart not less than $e$? It is easy to construct examples showing that if we keep $d$ fixed and allow $e$ to approach 0, then $B(e,d)$ approaches infinity. Questions like this arise in connection with some recent theories of physics in which space (and perhaps also time) is "quantized". There is a minimum length $e$. Furthermore, the maximum amount of information that can be contained in any bounded region of space is limited. This limit is proportional, not to the volume of the region, but to the surface area of its boundary. One final question: Are there any simple necessary and sufficient conditions on a finite set of points $S$ in $E^3$ for there to exist a (convex or nonconvex) polyhedron whose set of vertices is identical to $S$?

Concerning your last question (conditions for a set of points to be realized as the vertices of a polyhedron), it was established by Branko Grunbaum that every noncoplanar finite set of four or more points is the vertex set of a (closed, bounded) polyhedron in $\mathbb{R}^3$. His proof is constructive. It is described in, "Hamiltonian polygons and polyhedra," Geombinatorics, 3 (1994), 8389. It may not be easy to locate that paper, so you might instead look at the 2003 paper, "On Polyhedra Induced by Point Sets in Space," by Hurtado, Toussaint, and Trias (PDF link). They offer "better" (in some senses) constructions of realizing polyhedra, and fast algorithms: $O(n \log n)$ for $n$ points. And there have been further "improvements" on this work, notably in the 2010 paper, "BoundedDegree Polyhedronization of Point Sets," whose title states the improvement. This paper was presented at Canad. Conf. Comput. Geom. 2010, Winnipeg, and may be downloaded from that conference link. Here are figures from the latter two papers. The left figure, from the 2003 paper, hints at one
of the construction algorithms. The right figure, from the 2010 paper, shows one step of the
construction of a tunnel that connects two triangles, and ultimately connects to a face of the hull.


