CS 497 JE: Spring 2002

231 Natural History Building

## · 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(n^{2}+ 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(n^{2}) lower bound and Paterson and Yao's O(n^{2}) upper bound for 3d BSPs[Ke Chen] Mar 14 Line arrangments:definitions, complexity, incremental construction, The Zone Theorem[Guillermo Contu] Mar 19 Spring breakMar 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:01689Credit:1 unitPrerequisite:- 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 notesfor 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 notesexactlyas 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)

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