4
$\begingroup$

I'm interested in the following problem: I am given the combinatorial structure (vertices, edges, faces) and edge lengths of a polyhedron. From this I'd like to infer the vertex positions.

Now, I know that the above information does not uniquely determine the polyhedron. For instance, position and rotation are deliberate. But if I also pre-specify the positions of two connected vertices, then position and rotation of the polyhedron are determined.

My question is: Is the polyhedron completely determined then? If not, which additional information is needed? And is there a known algorithm for constructing at least one of the possible polyhedra from this information?

The application is to construct a 3D model of a house given the side lengths. If there is no algorithm for general polyhedra, maybe there is one for a subset of all possible house shapes? I assume simple house shapes here, i.e. all walls and roof sides are just single faces. The faces can, however, have 5 or more vertices and the house shapes do not have to be convex.

Thanks a lot in advance!

Daniel

$\endgroup$
  • 2
    $\begingroup$ Don't you need 3 vertices to fix position and rotation? $\endgroup$ – Jeff Snider Feb 3 '14 at 0:33
  • $\begingroup$ @JeffSnider Assuming you have a rigid body, yes. Two vertices fix the axis of rotation, and a third non-collinear vertex fixes the orientation about the axis. $\endgroup$ – David H Feb 3 '14 at 0:36
  • 1
    $\begingroup$ This is the topic of Rigidity Theory. In realizing a vertex-and-edge figure with hinges and rods, the degrees of freedom of motion can be very high, making the result flexible. In 2D, there are edge-counting rules that guarantee that a structure incorporates enough "struts" to be rigid. (See, for instance, Laman graphs.) I'm not sure what the state of the theoretical art is in 3D, but as answers show: the skeletal structure of a polyhedron is not always enough to ensure rigidity. $\endgroup$ – Blue Aug 2 '19 at 16:40
1
$\begingroup$

Consider 8 points, connected in a cube with edge lengths 1. The angles at the vertices are not determined, it can be rectilinear or collapse into a plane without changing edge lengths.

You can apply the goal of maximizing interior volume and you may achieve a unique solution, although I can't see how to prove it.

$\endgroup$
  • $\begingroup$ +1. This counterexample might even live in the class of "house shaped" polyhedra. $\endgroup$ – M. Winter Aug 2 '19 at 15:57
1
$\begingroup$

2-dimensional counterexample: even after you fix the positions of vertices $B,C,D$, it remains undetermined whether the fourth vertex falls at $A$ or $A'$.

enter image description here

$\endgroup$
0
$\begingroup$

enter image description here You might extend this into three dimensions as a prism.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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