Building a polyhedron from areas of its faces

2011-12-01T00:25:07Z

Is there a known algorithm which, given a finite multiset (unordered list) of integers $A$, returns a yes/no answer for "Is there a polyhedron such that the multiset of areas of all its faces is exactly $A$?"?

Is there a known general algorithm for $n$-dimensional polytopes?

Answer by Joseph O'Rourke for Building a polyhedron from areas of its faces

2011-12-01T01:36:49Z

I can answer your question with the specialization to convex polyhedra and polytopes. Specializing further to $\mathbb{R}^3$, the result is that

$n \ge 4$ positive real numbers are the face areas of a convex polyhedron if and only if the largest number is not more than the sum of the others.

I wrote up a short note establishing this: "Convex Polyhedra Realizing Given Face Areas," arXiv:1101.0823. The result relies on Minkowski's 1911 theorem, which perhaps you know:

Theorem (Minkowski). Let $A_i$ be positive faces areas and $n_i$ distinct, noncoplanar unit face normals, $i=1,\ldots,n$. Then if $\sum_i A_i n_i = 0$, there is a closed convex polyhedron whose faces areas uniquely realize those areas and normals.

This theorem reduces the problem to finding orientations $n_i$ so that vectors of length $A_i$ at those orientations sum to zero. And this is not difficult. Here is Figure 3 from my note from which you can almost infer the construction:

Minkowski's theorem generalizes to $\mathbb{R}^d$ and so does an analog of the above claim (but I did not work that out in detail in the arXiv note). In terms of an algorithm, the decision question is linear in the number $n$ of facet areas, and even constructing the polyhedron is linear in $\mathbb{R}^3$, and likely $O(dn)$ in $\mathbb{R}^d$ (but again, I didn't work that out).

But you don't mention the word "convex" in your post, so perhaps you are interested in nonconvex polyhedra and polytopal complexes?

Building a polyhedron from areas of its faces - MathOverflow

Building a polyhedron from areas of its faces

Answer by Joseph O'Rourke for Building a polyhedron from areas of its faces