For any homework help related queries, call us at: –
+1 678 648 4277
You can mail us at:- support@[Link] or
reach us at:- [Link]
Geometric Homework Help
Problem 1. Identify the shadow tree in the Tree Maker designs
given by the crease patterns below.
Solution: Given below by the light blue tree with length labels.
Problem 2. Identify all paths that are active at any time during the
universal molecule construction process (not just at the beginning),
in the TreeMaker diagrams given by the crease patterns above.
Solution: Given below.
Problem 3. Given a flat-foldable
degree-4 vertex, we can represent its
configuration in 3D space by the
four angles between the creases
(θ1,θ2,θ3,θ4) and by four folding
angles (ρ1,2,ρ2,3,ρ3,4,ρ4,1), as
shown on the right. We measure a
folding angle between −180◦ and
180◦: a folding angle of 0 indicates
no folding, while a folding angle of
±180◦ indicates a mountain/valley
flat fold. Prove that, for any 3D
configuration of a flat-foldable
degree-4 vertex, |ρ1,2| = |ρ3,4| and |
ρ2,3| = |ρ4,1|. (For the mountain-
valley assignment in the figure, ρ1,2
= ρ3,4 and ρ2,3 = −ρ4,1.) 2,3 ρ θ 2 θ
3 θ 4 ρ Hint: Use spherical
trigonometry.
Solution: Choose points along the creases all at distance 1 from
the vertex of the fold. These points form a spherical quadrilateral
on the surface of a sphere of radius 1, whose edge lengths are θ1,
θ2,θ3,θ4, and whose vertex angles are ρ1,ρ2,ρ3,ρ4. Call the
interior diagonal of this quadrilateral x. Then, by the Spherical
Law of Cosines, we have:
Further, by Kawasaki’s Theorem, we know:
θ1 +θ3 = θ2 +θ4 =π.
From trigonometry, we know:
‘cos(π − θ) = −cosθ, ‘
sin(π − θ) = sinθ.
Combining Equations 1 through 6, we get:
cosx = cosθ2cosθ3 +sinθ2sinθ3cosρ2,3 = cosθ1cosθ4 +
sinθ1sinθ4cosρ4,1
cosθ2 cosθ3 + sinθ2 sinθ3 cosρ2,3 = cos(π − θ3)cos(π − θ2) + sin(π
− θ3)sin(π − θ2)cosρ4,1
cosθ2 cosθ3 + sinθ2 sinθ3 cosρ2,3 = (−1)(−1)cosθ2 cosθ3 +
sinθ2sinθ3 cosρ4,1
cosθ2 cosθ3 + sinθ2 sinθ3 cosρ2,3 = cosθ2 cosθ3 + sinθ2sinθ3
cosρ4,1
cosρ2,3 = cosρ4,1
Because we know the values of our fold angles are restricted to the
range [−π,π], we know ρ2,3 = ±ρ1,4. A similar argument using
different angles and spherical triangles gives the other pair of
angles.
Problem 4. Prove that the following problem is NP-hard:
Given a 1D piece of paper with a 1D crease pattern, find the subset
of creases to fold that produces the smallest length of the resulting
flat folding.
Note that not all creases need to be folded and there is no
mountain-valley assignment.
Hint: Reduce from Partition.
Solution: We prove NP-hardness of the above problem by
reduction from Partition. The Partition problem asks, given a
multi-set S = {a0,a1,...,an}, whether there exists a partition into
two subsets S1 and S2 such that the sum of the elements of S1
equals the sum of the elements of S2. We construct an instance of
the folding problem with creases placed with the following
distances between them: {L,L/2,a0,a1,...,an,L/2,L}, where T = n
i=0ai and L > 2T.
Because of the edges of length L, it is impossible to fold the
paper smaller than length L. To achieve this minimum length,
both bars of length L must lie on top of each other, and thus the
bars of length L/2 must have endpoints at 0,L/2 or L/2,L. This
property can occur only if the sections in the middle come back
to the same location they start at, i.e., position L/2. Now, when
we decide not to fold a crease, we have lengths continuing in the
same direction, while when we fold the crease, they then move
in the opposite direction. Thus, to have the start and end of this
subsection of the paper return to the same place, we must be able
to pick lengths traveling to the right and lengths traveling to the
left such that the sum of the lengths in each group is the same.
(You may have noticed a similarity to Kawasaki’s Theorem,
because in that case the paper needed to meet itself to be
circular.)
Thus, we can instantiate the Partition problem in the folding
problem. If the minimum length is L, then we know that there is
a partition of the sets. In addition, if we know the partition, we
can construct a folding of length L by folding a crease whenever
the next corresponding segment is partitioned into a different set
than the previous one, and not folding a crease when they are
both in the same set. Therefore the folding problem is NP-Hard.