Computational geometry is the study of geometric problems from a computational point of view. Geometric algorithms appear in places both expected and unexpected. Some of the areas that require knowledge of geometric methods include graphics, computational biology, computer vision, robotics, geographic information systems, sensor networking, databases, and many other areas. At the core of computational geometry is a set of tools and techniques that are integral to dealing with geometric data, and these are what we will study in this class.
Geometric algorithms appear in places both expected and unexpected. Some of the areas that require knowledge of geometric methods include graphics, computational biology, computer vision, robotics, geographic information systems, sensor networking, databases, and many other areas.
This course will cover the fundamentals of geometric algorithms, as well as some of the numerous applications in which computational geometry plays an important role. The core topics covered will include convex hulls, Voronoi diagrams and Delaunay triangulations, arrangements, projective duality, range searching data structures, randomization, geometric approximations and combinatorial geometry. Depending on student interest and time, other topics covered will be some subset of high-dimensional geometry, geometric methods in data analysis (nearest neighbours, clustering, etc), geometric algorithms for large data sets, surface reconstruction, computational topology, and information geometry.
Textbook:
- Computational Geometry: Algorithms and Applications. M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Springer, 2000. (CGAA)
Lecture Outline
| Date | Topic | Scribe | Notes |
|---|---|---|---|
| Fundamental Geometric structures | |||
| Jan 9 | Convex Hulls in 2D. Jarvis March and Graham Scan | SV | |
| Jan 11 | Convex Hulls in 2D continued. 3D Hulls. The Upper Bound Theorem | SV | Assignment 1 (due 1/23; tex source and style file) |
| Jan 16 | Duality and arrangements. Zone Theorem. | Harsh Doshi | [CGAA Chap. 8] |
| Jan 18 | Voronoi Diagrams | Samuel Baird | [CGAA Chap 7]. A beautiful applet that demonstrates Fortune's algorithm step by step. |
| Jan 23 | Delaunay Triangulations | Carson Brownlee | [CGAA Chap. 9]. Delaunay applet. Assignment 2 (due Feb 8; tex) |
| Jan 25 | Delaunay Triangulations (cont.) | Linh Ha | |
| Geometric Searching | |||
| Jan 30 | Point Location, Trapezoidal Decompositions and Triangulations I | Brandon Hoff | [CGAA Chap. 6] |
| Feb 1 | Point Location, Trapezoidal Decompositions and Triangulations II | Thiago Ize | [CGAA Chap. 3] |
| Feb 6 | 1D Range Searching, K-d trees | Patrick Kelly | [CGAA Chap. 5] |
| Feb 8 | Quad Trees, Interval and Segment trees | David Koop | |
| Feb 13 | Benjamin Mabey | ||
| Feb 15 | John-Paul Ownby | ||
| Feb 20 | Pankaj Nathani | ||
| Feb 22 | Blake Nelson | ||
| Feb 27 | Piyush Rai | ||
| Mar 1 | Chelsea Robertson | ||
| Mar 6 | Austin Robison | ||
| Mar 8 | Mathias Schott | ||
| Mar 13 | Jianrong Shu | ||
| Mar 15 | Huy Vo | ||
| Mar 27 | Brian Young | ||
| Mar 29 | SV | ||
| Apr 3 | SV | ||
| Apr 5 | SV | ||
| Apr 10 | SV | ||
| Apr 12 | SV | ||
| Apr 17 | SV | ||
| Apr 19 | SV | ||
| Apr 24 | SV | ||
| Apr 26 | SV | ||
| May 1 | |||
| May 3 | |||
Course Mechanics
There will be 4-5 homeworks, and a project. The homeworks will be mostly pen-and-paper assignments. Projects can have a more theoretical or more programming-oriented flavor; students are welcome to come up with topics, or choose from a list provided. It will be expected that students give a presentation and a detailed writeup on their work (if programming is involved, the presentation will include a demo). There will be no exams.
Scribing Instructions
Students will be expected to scribe one lecture each. The LaTeX style file for scribing is here. If you are not familiar with LaTeX, then this guide might help.
Samples of scribed lectures:
Guide:- Scribed lectures MUST be turned in a week from the day of the lecture. At this point, there will be a round of revisions, and the final notes will be placed on the web 2 days after. Your fellow students are counting on these notes, so please be prompt and thorough.
- A LaTeX file and source for all supporting pictures must be handed in
- Use a .bib file to create references (the sample scribe lectures show how to include a .bib file and how to cite references). The ACM digital library stores pre-written BibTeX for most papers in its repository (whether or not the paper itself is available), and the Geombib search page is a useful, if occasionally outdated web search page that returns BibTeX entries. If you can't find a reference, ASK ME.
- For preparing pictures, you can use whatever software you like. If you're using the LaTeX - DVI - PDF pipeline, then you'll need .eps files, which can be prepared using Xfig or Ipe. If you're using the direct PDFLaTeX pipeline, then you'll need PNG/JPG/GIF/PDF files. THe first three can be created in any drawing program, and for the last, you'll need Acrobat/Xfig/Ipe.