Building a polyhedron from areas of its faces - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T21:39:36Z http://mathoverflow.net/feeds/question/82333 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/82333/building-a-polyhedron-from-areas-of-its-faces Building a polyhedron from areas of its faces Vladimir Reshetnikov 2011-12-01T00:25:07Z 2011-12-01T02:14:36Z <p>Is there a known algorithm which, given a finite multiset (unordered list) of integers $A$, returns a yes/no answer for <code>"Is there a polyhedron such that the multiset of areas of all its faces is exactly $A$?"</code>? </p> <p>Is there a known general algorithm for $n$-dimensional polytopes?</p> http://mathoverflow.net/questions/82333/building-a-polyhedron-from-areas-of-its-faces/82338#82338 Answer by Joseph O'Rourke for Building a polyhedron from areas of its faces Joseph O'Rourke 2011-12-01T01:36:49Z 2011-12-01T01:36:49Z <p>I can answer your question with the specialization to <em>convex</em> polyhedra and polytopes. Specializing further to $\mathbb{R}^3$, the result is that</p> <blockquote> <p>$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.</p> </blockquote> <p>I wrote up a short note establishing this: "Convex Polyhedra Realizing Given Face Areas," <a href="http://arxiv.org/abs/1101.0823" rel="nofollow">arXiv:1101.0823</a>. The result relies on Minkowski's 1911 theorem, which perhaps you know:</p> <blockquote> <p><b>Theorem (Minkowski)</b>. 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.</p> </blockquote> <p>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: <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/CylinderCylinder.jpg" alt="Cylinder-Cylinder"><br /></p> <p>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).</p> <p>But you don't mention the word "convex" in your post, so perhaps you are interested in nonconvex polyhedra and polytopal complexes? </p>