Computational Geometry
CS 497 JE: Spring 2002

Jeff Erickson

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

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



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
upper envelope of paraboloid tangent planes
^^^ lift ^^^   vvv project vvv
Delaunay triangulation combinatorial
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



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 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

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

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]
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.]
A. Bykat. Convex hull of a finite set of points in two dimensions. Information Processing Letters, 7:296-298, 1978. [Quickhull]
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.
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]]
Timothy Chan*. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry 16:361-368, 1996. ["Shatter-hull"]
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.
William F. Eddy. A new convex hull algorithm for planar sets. ACM Trans. Math. Software 3(4):398-403, 1977. [Quickhull]
Ronald L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters 1:132-133, 1972.
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]
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.]
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.
Michael Kallay. Convex hull made easy. Information Processing Letters 22(3):161, 1986. [O(n log n) incremental insertion]
Avraham A. Melkman. On-line construction of the convex hull of a simple polyline. Information Processing Letters 25:11-12, 1987.
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]
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]
Rephael Wenger. Randomized quick hull. Algorithmica 17:322-329, 1997. [O(n log h) expected-time prune and search same as [BS97]]


There are hundreds more of these.
Alejo Hausner*. Convex Hulls, February 1999. [Graham's scan, Jarvis march, and quickhull]
Tim Lambert. Convex Hull Algorithms, September 1998. [incremental, gift-wrapping, divide and conquer, and quickhull; in 2D and 3D]


UI Direct call number: 01689
Credit: 1 unit
CS 373 or equivalent, or my permission.
Mathematically and/or algorithmically mature undergraduates are welcome!!
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.

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

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.

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 ( 07 Apr 2002