· Course Announcement · Schedule · Homeworks · References · Administrivia ·
Announcements
- Homework 2 solutions are available.
- Homework 3 is due March 28.
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
- Homework 1, due February 5.
- Homework 2, due February 28.
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.
References*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.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)