TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Wednesday, January 30, 2013

On Reconstructing Convex Polyhedra



Ramana Rao and I were pondering the following basic question: one can always take a convex polyhedron, break it at all edges until only face polygons remain. Is it possible to do the reverse uniquely? ie, given a set of disconnected polygons (of course, with some edges of these different 'faces' having equal lengths so they can be hinged along them), can one always get a unique convex polyhedron?

Note: the problem does not allow faces to be merged into larger faces. Else, given (say) a set of identical squares, one can merge them into various sets of 6 rectangles each and form many different cuboids.

Prof. Gunter Ziegler told us out something very interesting - a very pleasing example.

http://en.wikipedia.org/wiki/Rhombicuboctahedron. About half way down the above page are two objects - the rhombicuboctahedron and the pseudorhombicuboctahedron. Both these convex polyhedra have the same sets of faces - 8 triangles, 18 squares. So if one is given only the faces, one is not sure which was the polyhedron from which the faces were broken off. Indeed, both polyhedrons are solutions to the reconstruction problem and they differ by a twist.

And here is a simpler example: take a cube of side a and 2 square pyramids of base with side a and height less than a/2. Two different convex polyhedra with same face sets result by attaching the pyramids on (1) opposite faces of the cube and (2) adjacent faces of the cube.

That brings up some further questions:

1. Is there some quantity invariant among all distinct convex polyhedra formable from any given face set? an obvious and very tempting candidate is volume - because the rhombi and pseudorhombi have the same volume of course. Same is the case with the two cube-pyramid concoctions too! Note: in 2D, things may be quite different. Indeed, in 2D, given a set of line segments, one could have convex polygons of hugely varying areas - with 4 equal segments we have either a square and rhombuses of arbitrarily low area.

2. let us say, for a given set of disconnected faces, a certain number of distinct convex polyhedra can be assembled. can some bound on their number, in terms of the number of faces be found? And if a face set were found that yields different convex polyhedra of different volumes, could one have some bound on the ratios between the max and min volumes?

3. And finally, what happens in higher dimensions - convex polytopes assembled from a set of hyperfaces?