MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Some questions about polyhedra in 3-dimensional Euclidean space, E3

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 non-convex) polyhedron whose set of vertices is identical to $S$?

-
The previous version of this question stopped in the middle of the first sentence, since the less than sign looked like it was starting an HTML tag. I've cleaned up the TeX and fixed one typo (B(d,e) vs. B(e,d)), but otherwise left the wording the same. – Henry Cohn Oct 14 at 16:01
I don't think your physics interpretation is right. If the Planck length was a minimum length scale, then it could be reduced further by a Lorentz transformation. In loop quantum gravity, for example, it's area and volume that are quantized, not length. This makes more sense, because Lorentz transformations preserve volume in the sense that the Jacobian determinant is 1. There were theories such as doubly special relativity (DSR) that did have a fixed minimum length, but DSR basically didn't work out. – Ben Crowell Oct 14 at 22:35
I must confess that my knowledge of physics is limited to what I learn from books written to explain the latest theories to non- physicists. My main interest is in what kinds of metric geometry enable you to put a lower bound on the "smallness" of point sets in E^3. How do you define "smallness" in this situation and for which point sets is it defined? If you fix the volume of a region in E^3 how do you limit the size of its surface area when all distances are allowed to be arbitrarily small. It was this sort of question I was thinking about. – Garabed Gulbenkian Oct 15 at 18:35
It does seem like an intrinsically intersting question in Euclidean geometry. I'm just not sure how well it maps onto the physics. In the applications we're talking about, the surfaces of interest are typically event horizons in vacuum solutions of the Einstein field equations. – Ben Crowell Oct 16 at 0:17

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 non-coplanar 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), 83-89.

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, "Bounded-Degree 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.

-
 This is an even better answer than I hoped for and I really appreciate it. – Garabed Gulbenkian Oct 14 at 19:53