Transcript Convex Polyhedra - Microsoft Research

Unfolding and
Reconstructing
Polyhedra
Brendan Lucier
University of Waterloo
Master’s Thesis Presentation
University of Waterloo, Waterloo, Ontario
January 2006
Outline

Unfolding Polyhedra
 Introduction
 Ununfoldable
Polyhedra
 Convex Polyhedra

Reconstructing Polyhedra
Outline

Unfolding Polyhedra
 Introduction
 Ununfoldable
Polyhedra
 Convex Polyhedra

Reconstructing Polyhedra
Unfolding Polyhedra





We consider the act of cutting a polyhedron along its edges and unfolding
it into the plane.
The resulting planar figure is an edge unfolding.
Two faces of the unfolding overlap if they have a common interior point.
An unfolding with no overlap is a simple unfolding, or net.
A polyhedron with no net is referred to as ununfoldable.
Unfolding with Overlaps
Image due to W. Schlickenrieder, “Nets of Polyhedra,” 1999
Unfolding with Overlaps
Image due to W. Schlickenrieder, “Nets of Polyhedra,” 1999
Simple Unfolding
Image due to W. Schlickenrieder, “Nets of Polyhedra,” 1999
Definitions




A convex set is one where
the line between two points in
the set remains in the set.
A face angle of a polyhedron
is an interior angle in a face.
The total face angle of a
vertex is the sum of its face
angles.
The curvature of a vertex is
360 minus its total face angle.
convex
nonconvex
positive
curvature
negative
curvature
Locality of Overlaps

An overlap is k-local if the
overlapping faces are
connected by a path of at
most k vertices in the
unfolding.
1-local overlap
2-local overlap
3- and 4-local overlaps
Outline

Unfolding Polyhedra
 Introduction
 Ununfoldable
Polyhedra
 Convex Polyhedra

Reconstructing Polyhedra
 Introduction
 Edge
Vectors
 Edge Lengths
History



1999: Bern, Demaine, Eppstein, and Kuo discover an
ununfoldable polyhedron with convex faces. This
polyhedron has 24 faces.
2002: Grünbaum constructs an ununfoldable convexfaced polyhedron with 13 faces.
2003: Bern, Demaine, Eppstein, Kuo, Mantler, and
Snoeyink construct an ununfoldable simplicial
polyhedron with 36 faces.
Images due to E. Demaine, “Folding and Unfolding,” 2001, and B. Grunbaum, “No-net Polyhedra,” 2002.
Describing 1-Local Overlaps



A 1-local overlap corresponds precisely to a situation in
which a vertex in an unfolding has total face angle
greater than 360o.
Convex polyhedra clearly avoid 1-local overlaps, since
they contain no vertices with negative curvature.
Motivating Question: does every polyhedron admit an
unfolding that contains no 1-local overlaps?
No!
v
Four-Pointed Star


Our polyhedron is a 4-pointed
star.
The polyhedron is
parameterized:


α (large) is the length of each
spike.
β (small) is the height of the center
points.
Argument


Claim: every unfolding of the 4pointed star contains a 1-local
overlap.
Main idea: To avoid 1-local
overlaps, we must cut at least
two opposing edges incident to
each B vertex.
Argument (con’t)



Our cuts must form a
spanning tree, so they
cannot form a cycle.
The cuts must
therefore be made as
shown in the bottom
diagram.
There is one final cut
that must be made.
Argument (con’t)



The center vertices have must
have at least 2 incident cuts (due
to negative curvature).
The remaining cut must therefore
be incident with both C vertices,
but they are not adjacent!
It is therefore impossible to cut
our 4-pointed star to avoid 1-local
overlaps.
Creating a Smaller Example



The 4-Pointed Star is an ununfoldable
polyhedron with 16 triangular faces.
We shall now make modifications to create a
smaller ununfoldable polyhedron.
The result will be an ununfoldable convex-faced
polyhedron with 9 faces.
Modification #1: 3-Pointed Star
Modification #2: Flatten



One side of the
polyhedron is flattened.
Two triangular faces are
combined into a single
quadrilateral face.
Think of the operation as
“cutting” the polyhedron
into two halves,
lengthwise.
Modification #3:



Perturb the symmetry of
the star by increasing the
angle between two
spikes.
This adds a new
parameter, φ, indicating
the angle change.
Perturbing by φ = 10o is
sufficient.
Unfolding This Polyhedron



At the B vertices with face
angles greater than 120,
two opposing edges must
be cut.
The vertices with
negative curvature must
each have two incident
cuts.
This leaves a few
possibilities for unfolding,
which are dealt with by a
case analysis.
Possible Unfoldings
Summary


There is a polyhedron with 16 triangular faces
for which every unfolding contains a 1-local
overlap.
There exists an ununfoldable, convex-faced
polyhedron with 9 faces.
Outline

Unfolding Polyhedra
 Introduction
 Ununfoldable
Polyhedra
 Convex Polyhedra

Reconstructing Polyhedra
History



1975: Shepphard conjectures that all convex polyhedra
can be unfolded without overlap.
1992-1993: Namiki and Fukuda create a Mathematica
package for unfolding polyhedra. Fukuda makes a
stronger conjecture about unfolding convex polyhedra.
1997: Schlickenrieder performs an empirical study of
various unfolding methods and makes further
conjectures about unfolding convex polyhedra.
2-local overlaps


Recall that an unfolding of a convex polyhedron
will never contain a 1-local overlap.
For convex polyhedra, we study 2-local
overlaps.
2-local overlap
Sufficient Conditions


We have no clean characterization of conditions for a 2local overlap, but we do have a set of sufficient conditions.
A 2-local overlap occurs from cut tree T if


a vertex v has an unfolding angle >270 incident with edge (v,w),
where w has degree 1, and
the curvature at w is sufficiently small.
Disproving Conjectures

We use the conditions from the previous slide as
follows:
 We
disprove certain conjectures of the form “every
convex polyhedron has a non-overlapping unfolding
of the form X.”
 For each unfolding type X, we construct a polyhedron
such that we obtain a 2-local overlap when we use X.
Conjecture #1: Shortest Path Tree

Given a polyhedron, a shortest path tree is created as
follows:





Choose a vertex v to be the root.
For every other vertex w, take the shortest path from v to w.
The union of all these paths is the shortest path tree.
Conjecture (Fukuda): If a convex polyhedron is cut
along a shortest path tree, the resulting unfolding will
not contain an overlap.
We shall disprove this conjecture.
Idea of Proof



Consider the illustrated graph
and shortest path tree.
Convert into a convex
polyhedron by raising the
internal vertices slightly;
shortest path tree remains the
same.
Also, curvatures will be as
small as we like, so the
conditions for a 2-local overlap
are satisfied.
Conjecture #2: Steepest Edge




Take a polyhedron and choose
a direction vector.
From each vertex, cut the edge
that is directed most toward
the chosen vector.
This forms the steepest edge
cut tree.
Conjecture (Schlickenrieder):
every convex polyhedron has
a steepest edge cut tree that
creates a non-overlapping
unfolding.
Disproving Schlickenrieder:


Steepest edge algorithm
applied to the graph at right
with direction “up.”
Get a cut tree that generates a
2-local overlap.
Disproving Schlickenrieder:




Steepest edge algorithm
applied to the graph at right
with direction “up.”
Get a cut tree that generates a
2-local overlap.
In fact, if the direction is
chosen to be close enough to
up, we get the same cut tree.
The given graph eliminates a
certain open range of choices
for directions.
Disproving Schlickenrieder (con’t)



Embed our graph in a triangle
and turn it into a convex terrain
by raising interior vertices.
Form a polyhedron by covering
the sphere with many
instances of this terrain.
Place instances in such a way
to cover all possible choices of
direction vectors.
Normal Order Unfoldings
Disproving Normal Order Unfoldings
Summary
We specified conditions on a cut tree that
generate a 2-local overlap.
 We created convex polyhedra for which
unfoldings of the following types have
overlaps:

 Shortest
path cut tree
 Steepest edge cut tree
Outline

Unfolding Polyhedra
 Introduction
 Ununfoldable
Polyhedra
 Convex Polyhedra

Reconstructing Polyhedra
Introduction


In the thesis we analyze the complexity of two
related decision problems:
Problem 1: Edge Vectors
 Given
a set of vectors, does there exist a
polygon/polyhedron with those vectors as edges (i.e.
edge lengths and orientations)?

Problem 2: Edge Lengths
 Given
a set of values, does there exist a
polygon/polyhedron with those values as edge lengths?

In this talk we will only discuss the Edge Vector
problem.
Edge Vector Reconstruction
We will look at many different types of
edge vector reconstruction problems.
 We attempt to reconstruct different things:

 Polygons
 Polyhedra
 Convex
Polygons/Polyhedra
 Orthogonal Polygons/Polyhedra
 etc.
Partition



Partition: given a set of positive integer values with a sum of 2S, is
there a subset of the values with a sum of S?
Partition is known to be an NP-hard problem.
Partition remains NP-complete if we require that all values are unique
and that our subset uses exactly half of the input values (shown in
thesis).
7
7
48
1
4
5
7
1 3
8
6
24
5
3
8
7
7
7
4 6
24
Review: Computational Complexity


We will be showing that some edge vector reconstruction
problems are NP-hard.
We do this by showing that if we can solve the edge
vector problem, then we can solve Partition with just a
little more work.



Given some input values (w1, …, wn) for the Partition problem,
we will create input values (i.e. a set of sticks) for our
reconstruction problem.
We will choose the input values so that the answer to our
reconstruction problem is “Yes” if and only if the answer to the
Partition problem is “Yes.”
This shows that reconstruction must be just as hard as Partition.
Problem 1: Degenerate Polygons


A degenerate polygon is one in which two incident edges are
collinear.
The edge vector problem is NP-hard for degenerate polygons.

Proof: Given an instance (w1, …, wn) of Partition, we create an instance
of the edge vector reconstruction problem with input
1
1
w1
w2
...
wn
Problem 2: Degenerate Polyhedra


Now extend to polyhedra.
The edge vector problem is NP-complete for degenerate polyhedra.

Given an instance (w1, …, wn) of Partition, create an instance of Edge
Vector with
w1
1
1
1
w2
1
S
1 1 1 1
...
wn
S
Problem 3: Convex Polygons



n/2
The edge vector problem for convex polygons is NP-complete.
We reduce from the version of Partition where the two sets must
have the same number of values and all values are unique.
Suppose (w1, …, wn) is an instance of Partition, with a sum of 2S.
Then our decision problem will have the following vectors:
B1
S
n/2
B2
S
Problem 3: Convex Polygons



n/2
The edge vector problem for convex polygons is NP-complete.
We reduce from the version of Partition where the two sets must
have the same number of values and all values are unique.
Suppose (w1, …, wn) is an instance of Partition, with a sum of 2S.
Then our decision problem will have the following vectors:
B1
n/2
B2
(S,n/2)
(S,n/2)
S
S
Problem 4: Convex Polyhedra





The edge vector problem is also NP-hard for convex polyhedra.
We build our solution upon that for convex polygons.
Create two copies of the polygon construction.
Add some vectors (0,0,1).
Then the only way these vectors can form a convex polyhedron is if
they create a prism, with our convex polygon as the base.
Summary of all results
Conclusion

Overarching idea: different ways to create
a polyhedron.
Thank You