CS 860: Algorithms for Polyhedra, Fall 2004
www.cs.uwaterloo.ca/~alubiw/polyhedra.html
Anna Lubiw,
Department of
Computer Science,
University of Waterloo
alubiw@uwaterloo.ca,
(519) 8884567, ext. 4449
Contents:
Organization,
Course Outline,
Resources,
Lectures,
Assign. 1,
Assign. 2,
Presentations.
Time and Place: Monday and Wednesay, 11:301:00, DC 3313,
starting Monday September 13.
Classes will consist of lectures,
student presentions of papers, and problem sessions.
Credit:
 3 assignments (30%)
 a class presentation of a journal or conference paper (30%). I will
suggest papers, or you may pick one yourself and check it with me.
 a written project (40%). Pick some topic that interests you
and is relevant to the course; explore some aspect of it;
read a few papers; and survey them in at most 6 pages. I will suggest
possible topics.
This will be a research level course in computational geometry,
concentrating on algorithms that deal with polyhedra in three dimensions.
Polyhedra have fascinated mathematicians for centuries, and this course
will at least touch on some of this large body of work, revisiting
classical results from a more algorithmic point of view.
These days, polyhedra and polygonal meshes are ubiquitous in computer graphics,
computer aided design, medical imaging,
and scientific computing; applicability to these areas
will guide the selection of topics for this course, although it
is not an applications course.
The course will emphasize design, correctness and analysis of algorithms.
Topics: (Preliminary list)
 basics on polyhedra and polygonal meshes
 fundamental theorems on convex polyhedra
 obtaining polyhedra from point sets  mesh generation and shape reconstruction
 obtaining polyhedra from parallel polygon slices
 obtaining polyhedra in solid modelling  operations on polyhedra
 decomposing polyhedra into simpler pieces
 Steinitz's theorem and Cauchy's theorem on convex polyhedra
 folding and unfolding polyhedra
 visibility, hidden surfaces, ray tracing
 shortest path problems
 motion planning
Background:
I will not assume that students have a previous course in computational
geometry, and will try to keep the overlap with our basic graduate course
in computational geometry, CS 763, as small as possible,
to avoid boring those who have taken, or will take that course.
I will assume a background in algorithms and data structures equivalent
to a decent undergraduate course.
 Polyhedra, P. Cromwell, Cambridge University Press, 1997.
A wonderfully illustrated and easytoread book on the
mathematics of polyhedra.
 Computational Geometry:Algorithms and Applications, M. de Berg,
M. van Kreveld, M. Overmars, O. Schwarzkopf, Springer, 1997.
A basic text on computational geometry.
 Computational Geometry in C (second edition), J. O'Rourke,
Cambridge University Press 1998.
(see the associated
web page.)
Web Pages
Polyhedra
Computational Geometry Algorithms and Software
Finding Papers
For each class, I've listed the topics covered, pages handed out, and
references.
Lecture 1, Sept. 13: Introduction to Polyhedra

Definition: A polyhedron is a finite set of plane
polygons called faces such that:
 if two faces intersect it is only at a common vertex or edge
 every edge of every face is an edge of exactly one other face
 the faces are connected
 the faces containing a vertex form a single circuit
Notes:
 this defines a polyhedron as a surface rather than a solid
 interior cavities are not allowed, and faces cannot have holes (in contrast
with solid modeling definitions)
 a polyhedron must be bounded, and live in 3D, but need not be convex
(in contrast with linear programming definitions)
 "tunnels" through the polyhedron are allowed (i.e. nonzero genus)
 Genus of a Polyhedron
 Various Polyhedra: Regular, Convex, Orthogonal
Handouts:
 Examples that are and are not polyhedra.
 Pictures to illustrate genus
References:
 O'Rourke's book (the chapter on convex hulls in 3D) covers most of this
material.
 Cromwell's book has more material, and more history.
Thought Exercise: which polyhedra make fair dice?
See
George Hart's dice page, MathWorld's isohedron page.
Open Problem:
Can all convex polyhedra be edge unfolded?
See the Open
Problems Project.
Lecture 2, Sept. 15: Classic concepts and results on polyhedra
 Euler's formula, von Staudt's proof for genus 0.
 the consequence that V, E, and F are linearly related
 Descartes Theorem on curvature
 winged edge data structure for polyhedra
References:
 von Staudt's proof can be found in Coxeter, Regular Polytopes,
Dover, 1973. (Cromwell also has this proof, but poorly explained.)
 see Cromwell for Descartes' theorem.
 the winged edge data structure can be found in O'Rourke's book
and also in Graphics Gems II.
Lecture 3, Sept. 20: Obtaining Polyhedra: I. from point sets
 ways to obtain polyhedra
 obtaining polyhedra from point sets: simplest is convex hull
 Convex Hull (point set P) = all convex combintations of points in P
 Omega(n log n) lower bound even in 2D
 there are O(n log n) algorithms in 2D
 a 3D O(n log n) algorithm: divide and conquer, Preparata and Hong '77
 notes about convex hull in higher dimension: the size of the convex hull
is more than linear in n, the number of points; and divideandconquer
is not useful.
 two convex hull methods useful in all dimensions: incremental
and graph traversal
 brief overview of the O(n^2)
incremental method in 3D, and mention of the
fact that when points are added in random order, the algorithm can
be implemented to run in expected time O(n log n)
 brief overview of the graph traversal method (aka gift wrapping)
in 3D, with run time O(n h), where h is the number of faces of the convex hull.
 mention of "outputsensitive" convex hull algorithms, and Timothy Chan's
algorithm with run time O(n log h).
References:
 for general material on convex hulls, see O'Rourke, or de Berg et. al.
 the divideandconquer convex hull algorithm is described in overview
in O'Rourke; for more detail see Edelsbrunner, Algorithms in Computational
Geometry, SpringerVerlag, 1987.
 the incremental 3D convex hull algorithm is described in detail in
O'Rourke's book.
 for a good survey of the state of the art in convex hulls, and
for information on convex hulls in higher dimensions, and more information
on the graph traversal method, see:
R. Seidel, Convex hull computations, in
Handbook of Discrete and Computational Geometry, 2nd edition,
J. E. Goodman and J. O'Rourke, editors,
chapter 22, CRC Press, 2004. (The first edition, from 1977, has this material
too.)
 for the output sensitive 3D convex hull algorithm see:
Timothy Chan,
Optimal outputsensitive convex hull algorithms in two and three dimensions,
Discrete & Computational Geometry, 16:361368, 1996.
Lecture 4, Sept. 22
 definition of Voronoi diagram
 brief history: Descartes, Dirichlet 1850, Voronoi 1908
 application: the post office problem
 Delaunay triangulation in 2D
 definition of Delaunay triangulation in general dimension
 Lemma. the Dealaunay triangulation is a simplicial complex
 duality between Delaunay triangulation and Voronoi diagram
 transformation from Delaunay triangulation to convex hull one dimension
higher
References:
 2D Voronoi diagrams and Delaunay triangulations are covered in
O'Rourke and in de Berg et al.
 For a survey of more advanced material, see
S. Fortune,
Voronoi diagrams and Delaunay triangulations,
Handbook of Discrete and Computational Geometry, 2nd edition,
J.E. Goodman, J. O'Rourke, eds., Chapter 23,
CRC Press, New York, 2004.
older version
Exercise: Find n points in 3D with Omega(n^2)
Delaunay tetrahedra.
Lecture 5, September 27
 alphashapes  definition and pictures
 the medial axis of a polygon/polyhedron
 the straight skeleton
 approximating the medial axis
References:
 H. Edelsbrunner and E. P. Mucke, ThreeDimensional Alpha Shapes,
ACM Transactions on Graphics 13, 1, 4372, 1994.
citeseer page from which you can obtain the paper.
 for a survey on surface reconstruction see:
T. K. Dey. Curve and surface reconstruction.
Chapter in Handbook of Discrete and Computational Geometry,
Goodman and O' Rourke eds., CRC press, 2nd edition. 2004.
gzipped postscript
 there is a brief description of the medial axis in O'Rourke's book.
For more general information see:
F. Aurenhammer and R. Klein. Voronoi diagrams. In J. Sack and G. Urrutia,
editors, Handbook of Computational Geometry, pages 201290. Elsevier
Science Publishing, 2000.
gzipped postscript.
 for a linear time algorithm in 2D see:
F. Chin, J. Snoeyink, and C.A. Wang.
Finding the medial axis of a simple polygon in linear time.
Proc. 6th Annu. Internat. Sympos. Algorithms Comput., pp. 382391.
Lecture Notes Comput. Sci. 1004, SpringerVerlag, 1995.
citeseer page where you can download the paper.
 for a medial axis algorithm in 3D see:
T. Culver, J. Keyser, D. Manocha, Accurate computation of the medial
axis of a polyhedron,
Proc. Fifth Symposium on Solid Modeling and Applications, pp. 179190, 1999.
citeseer page where you can download the paper.
implementation information.
 for information on the straight skeleton, see:
D. Eppstein, J. Erickson, Raising Roofs, Crashing Cycles, and
Playing Pool: Applications of a Data Structure for Finding Pairwise
Interactions, Symposium on Computational Geometry, 5867, 1998.
citesser page where you can download the paper.
Possible Papers to Present:
(Present an overview of the paper in 20 minutes.)
 the paper above by Chin, Snoeyink and Wang
 the paper above by Eppstein and Erickson
 M. Tanase and R. Veltkamp,
A Straight Skeleton Approximating the Medial Axis.
Proceedings European Symposium on Algorithms 2004, LNCS 3221, Springer,
809821.
pdf file
Possible Project:
 explore approximations to the medial axis
Lecture 6, September 29
 power diagrams
 overview of the power crust algorithm
References:
 the survey by Aurenhammer and Klein, listed above, covers power diagrams
 The power crust algorithm is from:
N. Amenta, S. Choi,
R. Kolluri, The power crust, unions of balls, and
the medial axis transform, Computational Geometry 19, 23, 127153, 2001.
citeseer page where you can download the paper.
web page.
Lecture 7, October 4
 reconstructing a polyhedron from a set of parallel planar crosssections
References:
 G. Barequet and M. Sharir, Piecewise linear interpolation between
polygonal slices, Computer Vision and Image Understanding: CVIU, 63, 2,
251272, 1996.
citeseer page with a preliminary version of the paper.
Final version as
gzipped postscript file.
Possible Papers to Present:
(Present an overview of the paper in 20 minutes.)
 K. Fujimura and E. Kuo, Shape Reconstruction from Contours
using Isotopic Deformation, CVGIP: Graphical Models and Image Processing,
Volume 61, Issue 3, Pages: 127  147, 1999.
Trellis page where you can download the paper.
 G. Barequet, M. Dickerson, and D. Eppstein,
On Triangulating ThreeDimensional Polygons, in Proc. 12th Annu.
ACM Sympos. Comput. Geom., pages 3847, Philadelphia, PA, USA,
1996.
citeseer page where you can download the paper.
Lecture 8, October 6
 obtaining polyhedra in solid modeling  Boolean operations on polyhedra,
and the issue of robustness
References:
 C. Hoffmann, J. Hopcroft, M. Karasick, Robust set operations on polyhedral
solids, IEEE Computer Graphics and Applications 9, 6, 5059, 1989.
 this topic is covered in books on solid modeling, in particular:
C. Hoffmann, Geometric and Solid Modeling: an Introduction,
Morgan Kaufman, 1989.
Possible Papers to Present:
(Present an overview of the paper in 20 minutes.)
 B. Chazelle, An optimal algorithm for intersecting threedimensional
convex polyhedra, SIAM J. Computing 4, 671696, 1992.
ACM portal.
Lecture 9, October 18
 decomposing polyhedrawe concentrate on partitioning into
triangles/tetrahedra
 triangulating polygons in 2D
 in 3D it is not always possible to tetrahedralize without adding
Steiner points
 deciding if a polyhedron can be tetrahedralized without Steiner points
is NPhard
 even without Steiner points, the number of tetrahedra is not unique,
and deciding the minimum number of tetrahedra needed for a convex
polyhedron is NPhard
 number of Steiner points required to triangulate a polyhedron
can be Omega(n^2)  Chazelle's example
 every polyhedron can be triangulated using O(n^2) Steiner points and O(n^2)
tetrahedra
References:

Bern and Eppstein, Mesh Generation and Optimal Triangulation, in Computing in
Euclidean Geometry,
edited by DingZhu Du and Frank Hwang, World Scientific, Lecture Notes Series on
Computing, Vol. 1,
1992.
citeseer page where you can download the paper.
 Bern, 25. Triangulations and mesh generation, Chapter 25 in
Handbook of Discrete and Computational Geometry, 2nd edition,
J. E. Goodman and J. O'Rourke, editors,
CRC Press, 2004.
Possible Papers to Present:
(Present an overview of the paper in 20 minutes.)
 Chazelle B. and Palios L., Triangulating a Nonconvex Polytope,
Discrete Comput. Geom., 5, 1990, 505526.
 M. Bern. Compatible tetrahedralizations. In
Proceedings of the 9th ACM Symposium on Computational Geometry, pages 281288,
1993.
ACM portal
 B.Chazelle and N.Shouraboura, Bounds on the size of tetrahedralizations,
In Proc. 10th ACM Symp. Computational Geometry , 231239, 1994.
ACM portal
Lecture 10, October 20
 optimizing triangulations: an introduction to mesh generation
 structured versus unstructured meshes
 the Delaunay triangulation (DT) and constrained Delaunay triangulation
(CDT)
 Theorem. In 2D the [constrained] Delaunay triangulation maximizes the
minimum angle.
 optimizing triangulations allowing Steiner points, possible approaches:
 add points and use the constrained Delaunay triangulation
 add points such that the Delaunay triangulation of the points
includes the desired edges
 other trinagulations (not Delaunay)
 optimizing triangulations in 3D
 badly shaped tetrahedra in 3D: needle, wedge, spindle, sliver, cap
References:
 most of this lecture was based on
pdf slides
of a talk by Jonathan Shewchuck.
 Jonathan Shewchuck has many
papers
on this topic too
 also see the references for Lecture 9
Possible Papers to Present:
(Present an overview of the paper in 20 minutes.)
 Bern, Eppstein, Gilbert, Provably good mesh generation,
J. Comput. Syst. Sci., 48 (3), 384409, 1994.
ACM portal,
citeseer.

S. A. Mitchell and S. A. Vavasis. Quality mesh generation in
higher dimensions. SIAM J. Computing, 29(4):13341370, 2000.
pdf of SIAM article
citeseer page
Lecture 11, October 25
 Cauchy's rigidity theorem
References:
 A Proof of Cauchy's theorem can be found in Chapter 6 of
Polyhedra, P. Cromwell, Cambridge University Press, 1997.
Lecture 12, October 27
 unfolding polyhedra into polygons
 folding polygons into polyhedra
References:

Marshall Bern, Erik D. Demaine, David Eppstein, Eric Kuo, Andrea Mantler, and J
ack Snoeyink, ``Ununfoldable Polyhedra with Convex Faces,'' Computational Geomet
ry: Theory and Applications 24, 2, 5162, 2003.
paper from Erik's home page
 A. Lubiw, J. O'Rourke,
When can a polygon fold to a polytope?,
Technical Report 048, Dept. Comput. Sci., Smith College, June 1996.
citeseer page

E. Demaine, M. Demaine, A. Lubiw, J. O'Rourke, I. Pashchenko.
Metamorphosis of the Cube,
in 8th Annual Video Review of Computational Geometry, Proc. of the 15th Annual A
CM Symposium on Computational Geometry, 1999, 409410.
Erik Demaine's
web page
on this topic, where you can see the video (though without the music).

T. Biedl, A. Lubiw, J. Sun,
When can a net fold to a polyhedron?
submitted to Computational Geometry Theory and Applications, 1999.
Eleventh Canadian Conference on Computational Geometry, U. British Columbia, 199
9, 14.
citeseer page

E. Demaine, M. Demaine, A. Lubiw, J. O'Rourke,
Enumerating foldings and unfoldings between polygons and polytopes,
Graphs and Combinatorics, volume 18, number 1, 2002, pages 93104.
ps file, or longer version from
arXiv.
Lecture 13, November 1
 Flattening Polyhedra and the connection to folding and cutting paper
References:
 this lecture was based on unpublished work by myself, Erik
Demaine, and Martin Demaine.
 for Fold and Cut, see
Erik Demaine's
web page on the topic.
Lecture 14, November 3
 Steinitz's Theorem
 the KoebeAndreevThurston Circle Packing (Coin Graph) Theorem
References:
 the proof of Steinitz's Theorem that I presented was from:
Lectures on Polytopes, G. Ziegler, SpringerVerlag, 1995.
 the circle packing theorem is also described in that book,
though not proved
 an algorithm for Steinitz's theorem on triangulated graphs is in:
G. Das and M. Goodrich, On the complexity of optimization problems for
3dimensional convex polyhedra and decision trees, Computational Geometry
8 (1997) 123137. (available online through Trellis)
 algorithms to find approximate coin graph representations can be found in:
 W. Smith, Accurate circle configurations and numerical
conformal mapping in polynomial time, 1991.
ps file
 B. Mohar, Circle Packings of Maps in Polynomial Time,
European Journal of Combinatorics 18, (1997) 785805.
pdf file
 C. Collins and K. Stephenson,
A Circle Packing Algorithm,
Computational Geometry: Theory and Applications, 25 (2003), pp. 233256.
Available online through trellis or from Stephenson's
web page.
Lecture 15, November 8: Shortest Paths
 review of Dijkstra's algorithm for shortest paths in a graph
 geometric shortest path problems, locally shortest paths
 shortest paths in a polygonal domain in 2D: continuous Dijkstra approach
 shortest path in 3D: NPhardness, approximation algorithms
 shortest path on a polyhedral surface: overview of algorithms
References:
 see this survey and its references:
J.S.B. Mitchell, Geometric Shortest Paths and Network Optimization.
versions of this appear in the Handbook of Computational Geometry
and the Handbook of Discrete and Computational Geometry.
.ps file
from Mitchell's home page
Lecture 16, November 8
 3 student presentations
 demonstration of foldandcut, left over from Lecture 13
Lecture 17, November 15
 1 student presentation
 descending paths on a polyhedral terrain
References:
 de Berg, van Kreveld, Trekking in the Alps without freezing or
getting tired, Algorithmica 18(3): 306323 (1997).
Lecture 18, November 17
 simplifying polyhedra
 for convex polyhedra:
 problem reduces to: find a "small" polyhedron between given inner
and outer polyhedra
 NPhard
 approximation algorithm: reduces to a setcover problem where randomized
natural selection does well
 for polyhedra terrains:
 can be reduced to a setcover problem (though size of solution grows
quadratically)
References:
 a survey of heuristic algorithms:
P. Heckbert and M. Garland. Survey of polygonal surface
simplification algorithms.
citeseer page
 convex polyhedra
 J. Mitchell and S. Suri,
Separation and approximation of polyhedral objects, Comput. Geom. Theory Appl.,
5 (2), 1995, 95114.
ACM portal
 H. Bronniman and M. Goodrich,
Almost Optimal Set Covers in Finite VCDimension, Discrete and
Computational Geometry (14), pages 463479, 1995.
.ps file
 polyhedral terrains:
 P. Agarwal and S. Suri,
Surface Approximation and Geometric Partitions.
SIAM J. Comput. 27(4): 10161035 (1998).
 P. Agarwal and P. Desikan, An efficient algorithm for
terrain simplification,
Proceedings of the eighth annual ACMSIAM symposium on Discrete algorithms,
(SODA), 1997, 139147.
ACM portal
Lecture 19, November 22
 1 student presentation
 ray shooting: best theoretical results
 ray tracing using triangulations: worst case and average case
bounds on stabbing number for triangulations
 cost prediction for ray shooting, and an octree construction
References:
 M. Pellegrini, Ray shooting and lines in space,
Handbook of discrete and computational geometry, ed. Goodman, O'Rourke, 2nd ed.
2004, pages 239256.
ps file of version from 1st edition

P. Agarwal, B. Aronov, S. Suri,
Stabbing triangulations by lines in 3D,
Proceedings of the Eleventh Annual Symposium on Computational geometry, 1995,
267276.
ACM portal
 B. Aronov and S. Fortune,
Averagecase ray shooting and minimum weight triangulations,
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997,
203211.
ACM portal
 B. Aronov, H. Bronnimann, A. Chang, Y. Chiang,
Cost prediction for ray shooting,
Proceedings of the Eighteenth Annual Symposium on Computational Geometry, 2002,
293302.
ACM portal
 B. Aronov , H. Bronnimann , A. Chang , Y. Chiang,
Costdriven octree construction schemes: an experimental study,
Proceedings of the Nineteenth Conference on Computational Geometry, 2003,
pages 227  236.
ACM portal
Lecture 20, November 24
 3 student presentations
 wrap up on polytope reconstruction
References:
Lecture 21, November 29
 1 student presentation
 Brendan Lucier: unfolding polyhedra
Lecture 22, December 1