Transcript Nonoverlap of the Star Unfolding

Nonoverlap of the
Star Unfolding
Boris Aronov and Joseph
O’Rourke, 1991
A Summary by Brendan Lucier, 2004
Outline
Introduction
 Definitions
 Basic Properties
 Main Theorem
 Algorithmic Consequences

Outline
Introduction
 Definitions
 Basic Properties
 Main Theorem
 Algorithmic Consequences

Introduction – What is this paper
about, and why do I like it?

It is a mathematics paper with algorithmic
consequences
 Proves
theorems and shows how they simplify
existing algorithms
Single-source shortest path queries (Chen and
Han, 1990)
 Finding edge sequences for shortest paths (Sharir
and Schorr, 1986)
 Computing geodesic diameter of a polyhedron
(Agarwal, Aronov, O’Rourke, and Schevon, 1990)

Outline
Introduction
 Definitions
 Basic Properties
 Main Theorem
 Algorithmic Consequences

Shortest Paths on a Polyhedron



We are given a convex
polyhedron P. We shall
refer to the vertices of P
as corners.
Given points x and y on a
polyhedron P, we shall
say “the shortest path
from x to y” to mean the
shortest path lying on the
surface of P.
Note that the shortest
path need not be unique.
Ridge Trees





Fix a point x on P. We shall call x
the source point.
We require that the shortest path
from x to each corner be unique.
A point y is a Ridge Point if there
are multiple distinct shortest paths
from x to y.
The set of all ridge points forms a
tree (not obvious) called the
Ridge Tree. A vertex of this tree is
a Ridge Vertex.
Note that the ridge tree touches
each corner (exercise: prove it).
The Star Unfolding





Take a convex polyhedron P with n corners.
Choose a point x on P with a unique shortest path to
each corner of P.
Cut P along the shortest paths from x to each corner.
Note that there will be n cuts.
Unfold the polyhedron into the plane.
This is a Star Unfolding Sx of P.
Example: Square Pyramid
b
a
c
A pyramid with source point and shortest paths to corners [a]. The star
unfolding with edge associations [b] and with the original polyhedron edges [c].
Outline
Introduction
 Definitions
 Basic Properties
 Main Theorem
 Algorithmic Consequences

Basic Properties of Star Unfoldings


Sx has 2n edges; two for
each cut made in the
polyhedron.
Pairs of corresponding
edges are adjacent.
Basic Properties (con’t)




The vertices of Sx are the
images of x and the n corners
of P.
Each corner has exactly one
image in Sx.
The other n vertices are all
images of x.
Each cut connects x to a
corner, so each edge must
connect an image of x to an
image of a corner.
Star Unfolding with Ridge Tree



We now add the ridge tree to the representation of Sx.
“Paint” the ridge tree onto the polyhedron, then unfold.
Notice that the ridge tree looks like a Voronoi diagram for the source
points xi. More on this later.
Outline
Introduction
 Definitions
 Basic Properties
 Main Theorem
 Algorithmic Consequences

Outline of Main Theorem

Theorem: The star unfolding Sx of any
convex polyhedron does not self-overlap.

We proceed by induction on n, the number of
corners of P.
The proof is split into the following steps:

1.
2.
3.
4.
Give a reduction from the star unfolding Sx, a polygon with 2n
sides, to a new polygon Sx’ with 2(n-1) sides.
Show that Sx’ is the star unfolding of a convex polyhedron.
Prove that non-overlap of Sx follows from non-overlap of Sx’.
Handle the base case.
Step 1: The Reduction



Lemma: there is a ridge vertex
v adjacent to two consecutive
corners pi, pi+1, whose sum of
curvatures is at most 2π.
Take the hexagon illustrated.
Remove pi and pi+1 and replace
them with p’. We position p’ so
its external angle equals the
sum of the curvatures of pi and
pi+1.
The resulting polygon is Sx’.
Reduction – Special Case




If n=4, then the sum of curvatures at any two corners could be 2π
(e.g. a regular tetrahedron).
It’s difficult to create point p’ with exterior angle 2π!
We handle this by placing p’ “at infinity,” so the polygon is infinite.
This case is handled separately.
a
b
c
A tetrahedron with source point and shortest paths [a], the star unfolding with polyhedron
edges shaded in gray [b], and the reduction to an infinite polygon (interior shaded) [c].
Step 2: Show S’ is a Star Unfolding



Alexsandrov’s Theorem: Every net that is homeomorphic to a sphere and
whose angle sum at every vertex is ≤ 2π corresponds to a closed convex
polyhedron.
The authors show that Alexsandrov’s Theorem applies to Sx’ (not too hard),
so Sx’ is an unfolding of some polyhedron P’.
The paper also proves that Sx’ is actually the star unfolding of P’.
S
S’
Step 3: Nonoverlap




Want to claim that Sx does not overlap if Sx’ does not overlap.
Problem: the edges in Sx can go “outside” the edges in Sx’.
Idea: Expand the unfolding to include “Sectors.”
A Sector is the exterior sector of the circle centred at a corner pi,
with points xi and xi-1 on its circumference.
Example: Pyramid Unfolding
Step 3 (con’t)



The authors show that Sx
plus sectors is contained
in Sx’ plus sectors.
It then follows that if the
“big” sector of Sx’ doesn’t
intersect any other part of
Sx’, then the two “small”
sectors of Sx won’t either.
This concludes the
induction step.
Step 4: Base Case



The base case occurs
when n=3.
This is not a polyhedron,
but a “doubly-covered
triangle” that is allowed
by Alexsandrov’s
Theorem.
The proof of the claim is
“easy” for the base case,
but too technical to get
into here.
Outline
Introduction
 Definitions
 Basic Properties
 Main Theorem
 Algorithmic Consequences

Voronoi Property




Let X be the set of
images of x in the star
unfolding.
Theorem: the ridge tree is
exactly the Voronoi
diagram of X, intersected
with the star unfolding.
A non-trivial corollary to
the induction argument.
The main idea is to view
the sectors as Voronoi
Disks.
Consequences of the Voronoi Property

It is now easy to construct the ridge tree:




Generate the star unfolding Sx.
Compute the Voronoi diagram V of X.
Restrict V to the interior of Sx.
This can be applied to previous algorithms:



Justifies “Single-source shortest path queries” (Chen and Han, 1990)
Simplifies the analysis of “Finding edge sequences for shortest
paths” (Sharir and Schorr, 1986)
Improves running time of “Computing geodesic diameter of a
polyhedron” (Agarwal, Aronov, O’Rourke, and Schevon, 1990)
Conclusion: This Paper…
developed some properties of Ridge Trees
and Star Unfoldings,
 proved that the Star Unfolding of a convex
polyhedron does not self-overlap, and
 applied this theorem to existing algorithms.

Fin.