Computational Geometry
CS 497 JE: Spring 2002

Jeff Erickson

TuTh 2:00-3:15
231 Natural History Building


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


Announcements


Schedule

Date Lecture topics Scribe notes
Jan 15 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's 373 notes
Jan 17 Two-dimensional convex hulls: sweep, incremental insertion, randomized incremental, prune and search, quickhull [Dan Cranston]
Jan 22 Geometric transformations: "Geometry" according to Euclid, Hilbert, Klein, Riemann, Thurston, and others; rigid, affine, projective, and conformal transformations; projective duality; linearization and projection [Katia Hayati]
Jan 24 [Chi-Sheng Shih]
Jan 29 Voronoi diagrams: definitions, incircle test, construction by depth-first search, divide and conquer [Greg Taylor]
Jan 31 Voronoi diagrams: Fortune's sweep
Delaunay triangulations: definitions, duality with Voronoi diagrams, local Delaunay condition, flipping
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
[Greg Taylor]
Feb 5 Randomized incremental Delaunay triangulations: Watson's incremental flipping algorithm, history dag, conflicts, backward analysis [Guest lecturer: Shripad Thite] [Dan Cranston]
Feb 7 Symbolic perturbation [Guest lecturer: David Bunde]  
Feb 12 Polytopes and polyhedra: definitions, equivalence of convex hulls (polytopes) and halfspace intersections (polyhedra), faces (facets, ridges, edges, vertices), the face lattice, polytope duality. [Amit Patel]
Feb 14 Higher-dimensional convex hulls: Chand and Kapur's O(nf) gift-wrapping (primal) or pivoting (dual) algorithm, upper bound on number of facets [Amit Patel]
Feb 19 Higher-dimensional convex hulls: Seidel's O(n2 + f log n) shelling (primal) or sweeping (dual) algorithm, cyclic polytopes [Dave Edwards]
Feb 21 Higher-dimensional convex hulls: randomized incremental algorithms: conflict graphs, single conflicts, flipping with history dags [Dave Edwards]
Feb 26 Simple polygon triangulation: existence, van Gogh's algorithm, monotone mountain decomposition, trapezoidal decomposition [Lana Labeznik]
Feb 28 Trapezoidal decompositions: plane sweep, randomized incremental construction, point location [Lana Labeznik]
Mar 5 Trapezoidal decomposition: Seidel's O(n log* n)-time randomized algorithm [Nathan Ramsey]
Mar 7 Binary space partitions: Basic definitions, Paterson and Yao's O(n log n) BSPs for segments in the plane [Ke Chen]
Mar 12 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 [Ke Chen]
Mar 14 Line arrangments: definitions, complexity, incremental construction, The Zone Theorem [Guillermo Contu]
Mar 19 Spring break
Mar 21
Mar 26 Hyperplane arrangments: definitions, The Zone Theorem (the basic recurrence) [Jongwoo Lim]
Mar 28 Hyperplane arrangments: The Zone Theorem (solving the basic recurrence; Euler's formula), finding minimum-volume simplices [Jongwoo Lim]
Apr 2 Linear programming: definitions, Megiddo's prune and search algorithm (for d<4) [Youngihn Kho]
Apr 4 Linear programming: Seidel's easy randomized incremental algorithm, Matousek-Sharir-Welzl/Kalai's "hidden dimension" algorithm [Feida Zhu]
Apr 9 Linear programming: MSW continued; Clarkson's three-layer algorithm [Sang-Chul Lee]
Apr 11 LP-type problems: definitions, examples (minimum-enclosing balls and ellipsoids) [Amit Kesari]
Apr 16   [Hsiao-Yu Chen]
Apr 18   [Hsiao-Yu Chen]
Apr 23   [Feida Zhu]
Apr 25   [Feida Zhu]
Apr 30   [Katia Hayati]
May 2   [Amit Kesari]
May 10 Semester projects due


Homeworks


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]


Administrivia

UI Direct call number: 01689
Credit: 1 unit
Prerequisite:
CS 373 or equivalent, or my permission.
Mathematically and/or algorithmically mature undergraduates are welcome!!
Textbook:
Computational Geometry: Algorithms and Applications by Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (Springer-Verlag, 2nd edition, 2000). I'll also distribute recent conference and journal papers in class and/or on the course web site.

Coursework:
Grades will be based on homeworks, scribe notes, and a semester project. There will be no exams.

Homework:
There will be a written homework assignment every 2-3 weeks. I don't expect everyone to solve everything completely, but you should turn in at least a partial solution for each problem. Each homework will include at least one open problem, but I don't promise to reveal which one it is.

Homework should be typeset in LaTeX and submitted in PostScript or PDF by email, as either a MIME attachment or a URL, although I will also grudgingly accept hardcopy printed or handwritten submissions. Groups of up to 3 people can submit a single solution.

Scribe notes:
Each student is responsible for latexing scribe notes for at least two (preferably consecutive) lectures, each due one week after the lecture itself. Here are a scribe notes latex package and some nonsense notes to get you started. I'll distribute the scribe notes exactly as they are submitted.

Since this is a geometry class, the scribe notes should contain lots of figures. I recommend idraw or Adobe Illistrator to generate PostScript images; if you don't have those, tgif and xfig are acceptable (but clunky) alternatives. For weirdos who like to describe their pictures instead of just drawing them, I recommend MetaPost or pstricks. If all else fails, draw it by hand and use a scanner.

Project:
Either a survey paper, a programming project, or (my favorite) original research. Details TBA.

I talk in pictures not in words.
- Peter Gabriel
"...And Through the Wire"
Peter Gabriel III (Melt) (1980)

I have no arguments to offer, my figures are my proofs.
Laugh away these truths and facts if you can.

- Theodore Heisel
The Circle Squared Beyond Refutation (1934)

CS 497 (Spring 2002) - Jeff Erickson (jeffe@cs.uiuc.edu) 07 Apr 2002