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
 Nonconvex
Polyhedra
 Convex Polyhedra

Reconstructing Polyhedra
 Introduction
 Edge
Vectors
 Edge Lengths
Outline

Unfolding Polyhedra
 Introduction
 Nonconvex
Polyhedra
 Convex Polyhedra

Reconstructing Polyhedra
 Introduction
 Edge
Vectors
 Edge Lengths
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
Simple Unfolding
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
 Nonconvex
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.
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 2π.
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!
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.
If B vertices occur at (±1, ±1, 0),
taking α = 10, β = 1 is sufficient.
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 2π/3,
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
General Unfoldings




In a general unfolding, we are allowed to cut a polyhedron across
faces, not just along edges.
Can our notion of 1-local overlaps provide a way to find polyhedra
with no non-overlapping general unfoldings?
No!
Theorem: Any polyhedron of genus 0 can be unfolded by arbitrary
cuts so that no vertex has an unfolding angle greater than 2pi.
Idea of Proof



From every vertex of the
polyhedron, separate the
total face angle into
components less than 2pi
by small straight-line cuts.
Connect these straightline cuts into a tree by
arbitrary curves.
Uses Euler’s formula and
some basic topology.
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.
Any polyhedron of genus 0 can be cut along
faces and unfolded so no vertex has an
unfolding angle greater than 2π.
Outline

Unfolding Polyhedra
 Introduction
 Nonconvex
Polyhedra
 Convex Polyhedra

Reconstructing Polyhedra
 Introduction
 Edge
Vectors
 Edge Lengths
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 w has degree 1 in T, say adjacent to v, where
vertex v has an unfolding angle greater than 270 incident with edge
(v,w), and
the curvature at w is sufficiently small (depending on the unfolding
angle).
Disproving Conjectures



We disprove certain conjectures of the form
“every convex polyhedron has a nonoverlapping unfolding of the form X.”
For each unfolding method X, we construct a
polyhedron such that we obtain a 2-local overlap
when we use X.
We do this by showing that the sufficient
conditions from the previous slide hold.
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.
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




Take a polyhedron and choose
a direction vector “up.”
Order faces by how much they
(I.e. their normals) face
upward.
A normal order unfolding is
one in which every face but the
lowest is connected to a lower
face.
Conjecture: Every convex
polyhedron admits a nonoverlapping normal order
unfolding.
Disproving the conjecture:


Same as steepest edge,
we just use a different
graph.
There are a few possible
cut trees, so we arrange
for each to create a 2local overlap.
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, and
 Normal order unfolding.
Outline

Unfolding Polyhedra
 Introduction
 Nonconvex
Polyhedra
 Convex Polyhedra

Reconstructing Polyhedra
 Introduction
 Edge
Vectors
 Edge Lengths
Introduction


We analyze the computational 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?
Review: Computational Complexity




We will be showing that problems are NP-hard.
A polytime reduction from problem A to problem B is a
polynomial-time algorithm to solve instances of A that
can use an oracle that instantly solves instances of B.
To show that a problem is NP-hard, one forms a polytime
reduction to it from a known NP-hard problem.
In our proofs, we use the Partition problem for
reductions.
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 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
Outline

Unfolding Polyhedra
 Introduction
 Nonconvex
Polyhedra
 Convex Polyhedra

Reconstructing Polyhedra
 Introduction
 Edge
Vectors
 Edge Lengths
Edge Vectors

We can restate the edge vector problem
as follows:
 Suppose
we are given a set of sticks floating
in space.
 We are allowed to translate these sticks, but
not rotate them.
 Under these conditions, can the sticks be
arranged to form a polygon/polyhedron of a
particular type?
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 edge vector with input


(0,1), (0,1)
(wi,0) for all i.
Degenerate Polyhedra


Now extend to polyhedra.
The edge vector problem is NP-complete for degenerate polyhedra.

Given an instance w_1, …, w_n of Partition, create an instance of Edge
Vector with




4x(0,0,1)
4x(0,1,0)
2x(S,0,0)
(w_i,0,0) for all i.
Convex Polygons



The edge vector problem for convex polygons is NP-complete.
We reduce from our strengthened version of Partition.
Suppose (w1, …, wn) is an instance of Partition. Then our decision
problem will have the following vectors:

xi = (wi, 1) for all i, and
 B1 = B2 = (S,n/2)
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.
Outline

Unfolding Polyhedra
 Introduction
 Nonconvex
Polyhedra
 Convex Polyhedra

Reconstructing Polyhedra
 Introduction
 Edge
Vectors
 Edge Lengths
Edge Lengths


We are given a pile of sticks, and asked whether they
can be glued together to form the edges of a
polygon/polyhedron.
It is known that this problem can be solved for polygons
in polynomial time, independent of degeneracy or
convexity.
 Namely, a polygon can be formed with given edge
lengths if and only if the longest value is less than the
sum of all the others.
Degenerate Polyhedra


Edge Length problem is NP-hard for
degenerate polyhedra.
Suppose (wi) is an instance of Partition,
with sum S. We provide lengths

wi for each i,
 a = 2S-1/2,
 b1 = b2 = S-1/3,
 c = 1/10.
Summary



It is NP-hard to determine whether a degenerate
polygon or polyhedron can be created from a set
of edge vectors.
It is NP-hard to determine whether a convex
polygon or polyhedron can be created from a set
of edge vectors.
It is NP-hard to determine whether a degenerate
polyhedron can be created from a set of edge
lengths.