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$
3
  • 2
    $\begingroup$ Don't you need 3 vertices to fix position and rotation? $\endgroup$ Feb 3, 2014 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, 2014 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, 2019 at 16:40

3 Answers 3

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$
1
  • $\begingroup$ +1. This counterexample might even live in the class of "house shaped" polyhedra. $\endgroup$
    – M. Winter
    Aug 2, 2019 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$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .