CS 860: Algorithms for Polyhedra, Fall 2004

Contents: Organization, Course Outline, Resources, Lectures, Assign. 1, Assign. 2, Presentations.

Organization

Time and Place: Monday and Wednesay, 11:30--1: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.

Course Outline

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

Books

• Polyhedra, P. Cromwell, Cambridge University Press, 1997. A wonderfully illustrated and easy-to-read 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

• David Eppstein's Polyhedra and Polytopes page from his Geometry Junkyard.
• George Hart's Encyclodedia of Polyhedra
• the polyhedra pages from MathWorld

Computational Geometry Algorithms and Software

• CGAL Computational Geometry Algorithms Library
• the computational geometry pages from MathWorld
• David Eppstein's Geometry in Action page.
• Joseph O'Rourke's comp.graphics.algorithms FAQ
• Graphics Gems

Finding Papers

• ACM Digital Library
• Computing Research Repository
• there are 3 computational geometry journals, Discrete and Computational Geometry, Computational Geometry Theory and Applications, and International Journal of Computational Geometry, all available in the UW library.
• Scientific Literature Digital Library (citeseer).
• Computational Geometry Bibliography

Lectures

Lecture 1, Sept. 13: Introduction to Polyhedra

• Definition: A polyhedron is a finite set of plane polygons called faces such that:
  1. if two faces intersect it is only at a common vertex or edge
  2. every edge of every face is an edge of exactly one other face
  3. the faces are connected
  4. 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 3-D, but need not be convex (in contrast with linear programming definitions)
  • "tunnels" through the polyhedron are allowed (i.e. non-zero genus)
• Genus of a Polyhedron
• Various Polyhedra: Regular, Convex, Orthogonal

• Examples that are and are not polyhedra.
• Pictures to illustrate genus

• O'Rourke's book (the chapter on convex hulls in 3-D) covers most of this material.
• Cromwell's book has more material, and more history.

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

• 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 2-D
• there are O(n log n) algorithms in 2-D
• a 3-D 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 divide-and-conquer 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 3-D, 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 3-D, with run time O(n h), where h is the number of faces of the convex hull.
• mention of "output-sensitive" convex hull algorithms, and Timothy Chan's algorithm with run time O(n log h).

• for general material on convex hulls, see O'Rourke, or de Berg et. al.
• the divide-and-conquer convex hull algorithm is described in overview in O'Rourke; for more detail see Edelsbrunner, Algorithms in Computational Geometry, Springer-Verlag, 1987.
• the incremental 3-D 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 3-D convex hull algorithm see:
  Timothy Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete & Computational Geometry, 16:361-368, 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

• 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

Lecture 5, September 27

• alpha-shapes -- definition and pictures
• the medial axis of a polygon/polyhedron
• the straight skeleton
• approximating the medial axis

• H. Edelsbrunner and E. P. Mucke, Three-Dimensional Alpha Shapes, ACM Transactions on Graphics 13, 1, 43--72, 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 201-290. Elsevier Science Publishing, 2000. gzipped postscript.
• for a linear time algorithm in 2-D 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. 382--391. Lecture Notes Comput. Sci. 1004, Springer-Verlag, 1995. citeseer page where you can download the paper.
• for a medial axis algorithm in 3-D 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. 179-190, 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, 58-67, 1998. citesser page where you can download the paper.

• 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, 809-821. pdf file

• explore approximations to the medial axis

Lecture 6, September 29

• power diagrams
• overview of the power crust algorithm

• 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, 2-3, 127-153, 2001. citeseer page where you can download the paper. web page.

Lecture 7, October 4

• reconstructing a polyhedron from a set of parallel planar cross-sections

• G. Barequet and M. Sharir, Piecewise linear interpolation between polygonal slices, Computer Vision and Image Understanding: CVIU, 63, 2, 251--272, 1996. citeseer page with a preliminary version of the paper. Final version as gzipped postscript file.

• 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 Three-Dimensional Polygons, in Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 38--47, 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

• C. Hoffmann, J. Hopcroft, M. Karasick, Robust set operations on polyhedral solids, IEEE Computer Graphics and Applications 9, 6, 50--59, 1989.
• this topic is covered in books on solid modeling, in particular:
  C. Hoffmann, Geometric and Solid Modeling: an Introduction, Morgan Kaufman, 1989.

• B. Chazelle, An optimal algorithm for intersecting three-dimensional convex polyhedra, SIAM J. Computing 4, 671--696, 1992. ACM portal.

Lecture 9, October 18

• decomposing polyhedra---we 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 NP-hard
• even without Steiner points, the number of tetrahedra is not unique, and deciding the minimum number of tetrahedra needed for a convex polyhedron is NP-hard
• 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

• Bern and Eppstein, Mesh Generation and Optimal Triangulation, in Computing in Euclidean Geometry, edited by Ding-Zhu 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.

• Chazelle B. and Palios L., Triangulating a Nonconvex Polytope, Discrete Comput. Geom., 5, 1990, 505-526.
• M. Bern. Compatible tetrahedralizations. In Proceedings of the 9th ACM Symposium on Computational Geometry, pages 281--288, 1993. ACM portal
• B.Chazelle and N.Shouraboura, Bounds on the size of tetrahedralizations, In Proc. 10th ACM Symp. Computational Geometry , 231--239, 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 3-D: needle, wedge, spindle, sliver, cap

• 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

• Bern, Eppstein, Gilbert, Provably good mesh generation, J. Comput. Syst. Sci., 48 (3), 384-409, 1994. ACM portal, citeseer.
• S. A. Mitchell and S. A. Vavasis. Quality mesh generation in higher dimensions. SIAM J. Computing, 29(4):1334--1370, 2000. pdf of SIAM article citeseer page

Lecture 11, October 25

• Cauchy's rigidity theorem

• 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

• 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, 51-62, 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, 409-410. 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, 1-4. 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 93-104. ps file, or longer version from arXiv.

Lecture 13, November 1

• Flattening Polyhedra and the connection to folding and cutting paper

• 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 Koebe-Andreev-Thurston Circle Packing (Coin Graph) Theorem

• the proof of Steinitz's Theorem that I presented was from:
  Lectures on Polytopes, G. Ziegler, Springer-Verlag, 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 3-dimensional convex polyhedra and decision trees, Computational Geometry 8 (1997) 123-137. (available on-line 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) 785-805. pdf file
  • C. Collins and K. Stephenson, A Circle Packing Algorithm, Computational Geometry: Theory and Applications, 25 (2003), pp. 233-256. Available on-line 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 2-D: continuous Dijkstra approach
• shortest path in 3-D: NP-hardness, approximation algorithms
• shortest path on a polyhedral surface: overview of algorithms

• 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 fold-and-cut, left over from Lecture 13

Lecture 17, November 15

• 1 student presentation
• descending paths on a polyhedral terrain

• de Berg, van Kreveld, Trekking in the Alps without freezing or getting tired, Algorithmica 18(3): 306-323 (1997).

Lecture 18, November 17

• simplifying polyhedra
• for convex polyhedra:
  • problem reduces to: find a "small" polyhedron between given inner and outer polyhedra
  • NP-hard
  • approximation algorithm: reduces to a set-cover problem where randomized natural selection does well
• for polyhedra terrains:
  • can be reduced to a set-cover problem (though size of solution grows quadratically)

• 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, 95-114. ACM portal
  • H. Bronniman and M. Goodrich, Almost Optimal Set Covers in Finite VC-Dimension, Discrete and Computational Geometry (14), pages 463--479, 1995. .ps file
• polyhedral terrains:
  • P. Agarwal and S. Suri, Surface Approximation and Geometric Partitions. SIAM J. Comput. 27(4): 1016-1035 (1998).
  • P. Agarwal and P. Desikan, An efficient algorithm for terrain simplification, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, (SODA), 1997, 139--147. 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

• M. Pellegrini, Ray shooting and lines in space, Handbook of discrete and computational geometry, ed. Goodman, O'Rourke, 2nd ed. 2004, pages 239-256. 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, 267--276. ACM portal
• B. Aronov and S. Fortune, Average-case ray shooting and minimum weight triangulations, Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997, 203--211. 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, 293--302. ACM portal
• B. Aronov , H. Bronnimann , A. Chang , Y. Chiang, Cost-driven 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

• E. Demaine and J. Erickson, Open problems on polytope reconstruction, associated web page

Lecture 21, November 29

• 1 student presentation
• Brendan Lucier: unfolding polyhedra

Lecture 22, December 1

• 4 student presentations