Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
There is one for two dimensions. If you don't mind prisms, you can likely adapt it to arbitrary dimensions. Gerhard "Ask Me About System Design" Paseman, 2011.11.30 –  Gerhard Paseman Dec 1 '11 at 1:34
add comment

1 Answer 1

up vote 13 down vote accepted

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:
            Cylinder-Cylinder

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?

share|improve this answer
    
Although I did not mention polygons, I suggested such in my comment above. There for n >=3 the condition is the same: no side must have length at least half the sum of all lengths. For arbitrary dimensions, I suspect the same holds true of any nontrivial polytope, convex or not: no k-face has k-measure at least half the sum of the k-measures of all k-faces. Triangular prisms should show that one cannot replace half by anything smaller. Gerhard "Ask Me About System Design" Paseman, 2011.11.30 –  Gerhard Paseman Dec 1 '11 at 1:53
2  
Let me mention that in a certain sense, the dual problem was resolved by Zil'berberg in 1962. This paper is not available in English I think, but is stated as Exercise 35.9 in my book: math.ucla.edu/~pak/book.htm There, the areas are replaced by curvatures, which satisfy the Gauss-Bonnet formula and the proof is via an easy reduction to Alexandrov's "ray theorem", which is dual to Minkowski's theorem (but neither easily implies another). –  Igor Pak Dec 1 '11 at 2:16
    
(cont'd) One curious extension of Zil'berberg's proof is that the polytope can be made simple (for even number of vertices). I bet your theorem extends to have all polytopes simpicial. –  Igor Pak Dec 1 '11 at 2:17
    
I should be more careful in my statements. Let a polytope live in R^d. For positive integral k less than d there is a constant c_(k,d) such that the sum of the measures of all k-faces of the polytope times that constant is greater than the k-measure of any single k-face. When k=d-1, I assert that the constant is 1/2. For smaller k, smaller constants are possible, and are likely to be c_(k,d)=1/(1+d-k). Gerhard "Ask Me About System Design" Paseman, 2011.11.30 –  Gerhard Paseman Dec 1 '11 at 2:17
    
As a remark to the case of an n dimensional non-convex polytope $P\subset \mathbb{R}^n$, Gerhard's condition is still necessary. Indeed, for any face f , the orthogonal projection onto the hyperplane containing that face is 1-Lipschitz and maps the n−1 skeleton of P minus f surjectively onto f (the easy reason is: f has an inner and an outer side (essentially by hypothesis on P, so that the line orthogonal to f at x∈f also meet ∂P in another y∉f). The analogous argument seems to work also for k-faces (giving the constant 1/2, possibly non optimal) –  Pietro Majer Dec 2 '11 at 11:55
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.