An uninflatable polyhedron

Computational Geometry

CS 598 JE, Spring 2008

WF 12:30-1:45, 1302 Siebel Center
Instructor: Jeff Erickson
http://www.cs.uiuc.edu/~jeffe/teaching/compgeom/

· Home · Course Announcement · Schedule · Homeworks · References · Administrivia ·

---

Schedule

This is still essentially the schedule from Spring 2002. I will update this semester's schedule as the semester progresses.

Makeup lectures for the cancelled classes on Jan 23, Feb 20, and Feb 22 will be held on three consecutive Mondays later in the semester.

Date	Lecture topics	Scribe notes
Jan 16	Two-dimensional convex hulls [O98, Chapter 3]: Definitions; counterclockwise test; Jarvis' march [J73], Graham's scan («das Dreigroschenalgorithmus») [G72, A79], divide and conquer [PH77], marriage before conquest [KS96]	[Jeff Erickson]
Jan 18	Two-dimensional convex hulls: sweep, incremental insertion, randomized incremental, prune and search, quickhull
Jan 23	Class cancelled — Jeff was at SODA
Jan 25	Geometric transformations: "Geometry" according to Euclid, Hilbert, Klein, and others; Euclidean, projective, and oriented-projective geometry	[Dan Schreiber]
Jan 30	Projective duality: point=line=vector=beer mug Voronoi diagrams: definitions, incircle test	[Dan Schreiber] [Evan VanderZee]
Feb 1	Voronoi diagrams: Shamos and Hoey's divide-and-conquer algorithm Delaunay triangultions: definitions, combinatorial dual of Voronoi diagram
Feb 6	Delaunay triangulations: Local Delaunay edges; Lawson's flipping algorithm Paraboloid lifting map: Delaunay triangulations lift to lower convex hulls
Feb 8	Paraboloid lifting map: lower convex hull of paraboloid points projective <---dual--> upper envelope of paraboloid tangent planes ^^^ lift ^^^   vvv project vvv Delaunay triangulation combinatorial <---dual---> Voronoi diagram Randomized incremental constructuon
Feb 13	Symbolic perturbation
Feb 15	Polytopes and polyhedra: definitions, equivalence of convex hulls (polytopes) and halfspace intersections (polyhedra), faces (facets, ridges, edges, vertices), the face lattice, polytope duality.
Feb 20	Class cancelled — Jeff will be at Dagstuhl
Feb 22
Feb 27	Higher-dimensional convex hulls: Chand and Kapur's O(nf) gift-wrapping (primal) or pivoting (dual) algorithm, upper bound on number of facets
Feb 29	Higher-dimensional convex hulls: Seidel's O(n2 + f log n) shelling (primal) or sweeping (dual) algorithm, cyclic polytopes
Mar 5	Higher-dimensional convex hulls: randomized incremental algorithms: conflict graphs, single conflicts, flipping with history dags
Mar 8	Simple polygon triangulation: existence, van Gogh's algorithm, monotone mountain decomposition, trapezoidal decomposition
Mar 12	Trapezoidal decompositions: plane sweep, randomized incremental construction, point location
Mar 14	Trapezoidal decomposition: Seidel's O(n log* n)-time randomized algorithm
Mar 19	Spring break
Mar 21
Mar 26	Binary space partitions: Basic definitions, Paterson and Yao's O(n log n) BSPs for segments in the plane
Mar 28	Binary space partitions: 2d BSPs continued, a sketch of Toth's lower bound for 2d BSPs, Chazelle's Omega(n2) lower bound and Paterson and Yao's O(n2) upper bound for 3d BSPs
Apr 2	Line arrangments: definitions, complexity, incremental construction, The Zone Theorem
Apr 4	Hyperplane arrangments: definitions, The Zone Theorem (the basic recurrence)
Apr 9	Hyperplane arrangments: The Zone Theorem (solving the basic recurrence; Euler's formula), finding minimum-volume simplices
Apr 11	Linear programming: definitions, Seidel's easy randomized incremental algorithm,
Apr 16	Linear programming: Matousek-Sharir-Welzl/Kalai's "hidden dimension" algorithm; Clarkson's three-layer algorithm
Apr 18	LP-type problems: definitions, examples (minimum-enclosing balls and ellipsoids)
Apr 23
Apr 25
Apr 30
May 2
May ??	Semester projects due

---

References

Pointers to free electronic papers were mined from ResearchIndex and authors' personal web pages. Papers from the ACM Digital Library and most journals require a subscription, and thus may be inaccessible from outside the uiuc.edu domain; I link to these only if no free version is available.

*Stars indicate authors who (as far as I know) were graduate students when their papers were first published. [No pressure!]

General References

[BKOS00]

Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2nd edition, 2000. [The required textbook]

[E01]

Jeff Erickson. CS 373: Combinatorial Algorithms. Lecture notes, 2001. See especially notes on convex hulls, plane sweep, and polygon triangulation. [Becuase I'm the professor, that's why.]

[O98]

Joseph O'Rourke. Computational Geometry in C. Cambridge University Press, 2nd edition, 1998. [An excellent introduction for students without a strong algorithms background. Source code is available from Joe's web site.]

Original Papers

[A79]

A. M. Andrew. Another efficient algorithm for convex hulls in two dimensions. Information Processing Letters 9(5):216-219, 1979. [A left-to-right variant of Graham's scan]

[AT78]

Selim G. Akl* and and Godfried T. Toussaint. A fast convex hull algorithm. Information Processing Letters, 7(5):219-222, 1978. [Another variant of Graham's scan with a quick pruning step.]

[B78]

A. Bykat. Convex hull of a finite set of points in two dimensions. Information Processing Letters, 7:296-298, 1978. [Quickhull]

[BIKMMT02]

Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison*, and Godfried T. Toussaint. Optimal in-place planar convex hull algorithms. To appear in Proceedings of Latin American Theoretical INformatics (LATIN 2002), 2002.

[BS97]

Binay Bhattacharya and Sandeep Sen. On a simple, practical, optimal, output-sensitive randomized planar convex hull algorithm. Journal of Algorithms 25:173-193, 1997. [O(n log h) expected-time prune and search; same as [W97]]

[C96]

Timothy Chan*. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry 16:361-368, 1996. ["Shatter-hull"]

[CSY97]

Timothy Chan*, Jack Snoeyink, and Chee Yap. Primal dividing and dual pruning: Output-sensitive construcion of 4-d polytopes and 3-d Voronoi diagrams. Discrete & Computational Geometry 18: 433-454, 1997.

[E77]

William F. Eddy. A new convex hull algorithm for planar sets. ACM Trans. Math. Software 3(4):398-403, 1977. [Quickhull]

[G72]

Ronald L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters 1:132-133, 1972.

[GS79]

Peter J. Green and Bernard W. Silverman. Constructing the convex hull of a set of points in the plane. Computer Journal 22:262--266, 1979. [Quickhull]

[GY83]

Ronald L. Graham and Frances F. Yao. Finding the convex hull of a simple polygon. Journal of Algorithms, 4:324-331, 1983. [One of several papers with this (approximate) title. O(n log n) sweep-insertion algorithm.]

[J73]

R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters 2:18-21, 1973.

[K86]

Michael Kallay. Convex hull made easy. Information Processing Letters 22(3):161, 1986. [O(n log n) incremental insertion]

[M87]

Avraham A. Melkman. On-line construction of the convex hull of a simple polyline. Information Processing Letters 25:11-12, 1987.

[PH77]

Franco P. Preparata and Se June Hong. Convex hulls of finite sets of points in two and three dimensions. Communications of the ACM 20(2):87-93, 1977. [O(n log n) divide and conquer]

[KS86]

David G. Kirkpatrick and Raimund Seidel*. The ultimate planar convex hull algorithm? SIAM Journal on Computing, 15(1):287-299, 1986. [O(n log h) "marriage before conquest" algorithm; Omega(n log h) lower bound]

[W97]

Rephael Wenger. Randomized quick hull. Algorithmica 17:322-329, 1997. [O(n log h) expected-time prune and search same as [BS97]]

Applets

There are hundreds more of these.

[H99]

Alejo Hausner*. Convex Hulls, February 1999. [Graham's scan, Jarvis march, and quickhull]

[L98]

Tim Lambert. Convex Hull Algorithms, September 1998. [incremental, gift-wrapping, divide and conquer, and quickhull; in 2D and 3D]