CSE 546: Computational Geometry, Fall 2016
This course considers data structures and algorithms for spatial data sets, collections of points, lines, planes, polygons and polyhedra that live in 2 or 3 dimensional space. These data structures form the basis for modern work in Computer Graphics, Geographic Information Systems, and, to a lesser extent, Computer Vision and Machine Learning.
Time and Room:on T,Th, 2:30-4:00, Crow 206
Textbook:"Computational Geometry: Algorithms and Applications", Third Edition. This textbook is highly recommended. It is a fantastic book, and relatively inexpensive. The Second or First edition of the textbook is acceptable. I also recommend reading Dave Mount's (wonderful) Lecture Notes. Suggested readings from the book and the lecture notes are highlighted below.
Course Discussions:There is a Piazza page to enable questions and discussions about the course materials. You can sign up with this link: piazza.com/wustl/fall2016/cse546, and the link to the course page is piazza.com/wustl/fall2016/cse546/home.
Academic Integrity:You are required to be familiar with and follow the academic integrity policy posted on this page, which is essentially copied from the policies of Jeremy Buhler in 441/541.
Class ResourcesA page with a collections of useful pointers to online resources for this class.
Office Hours:Robert Pless, Wednesday 11-12, Jolley 404
TA office hours will be announced soon.
Voronoi Diagrams and Delauney triangulations are data structures to reason about points and regions in space...
... not to be confused with the abstract, Paul Klee like work of Robert Delaunay.
Final Exam Topics
- Duality (Dual of a point, of a line, of a line segment, of a slab. Given a set of points, what is the dual of the set of points? what is the dual of its convex hull? Ham-Sandwhich cuts.
- Zone Theorem and applications of arrangements. Constructing an arrangement. size (number of vertices edges and faces of the arrangement).
- K-D trees. Construction. Rectangle searches (counting and reporting)
- Orthogonal Range Trees and Fractional Cascading.
- Nearest Neighbor Searching with KD trees
- Lecture 1, Intro to class, definition of convex and convex hulls, and degenerate point configurations. Reading: Chapter 1 of recommended textbook, Lecture 3 from Dave Mount's Lecture Notes
- Lecture 2, Relationship between Convex Hulls and Sorting, introduction to lower bound arguments. Key parts of this lecture are here: approximate lecture Notes.
- Lecture 3, Output Sensitive Complexity and Optimal Convex Hull Algorithms. approximate lecture Notes.
- Lecture 4, Line Segment intersection as examplar of Plane Sweep Algorithms. [Read, before this lecture, Section 2.1, on line segment intersection]. Lecture notes (from Subhash Suri, who was faculty at Washington University until 2000). Prezi.
- Class question: "What is the lower bound on counting (but not reporting) a collection of intersections. This is answered here in Section 38.3. Short answer. Detecting if there is ANY intersection taken at least O(n log n). There is an O(n log n + k) algorithm to report all possible intersections (where k is the number of intersections).
- Lecture 5. Planar Subdivisions, Double connected edge lists, Euler's Theorem, Lecture notes (from Subhash Suri, who was faculty at Washington University until 2000). Another set of Notes.
- Lecture 6. Art Gallery Theorem, intro to triangulation. Lecture Notes!. Extras: Holes.
- Lecture 7. Polygon triangulation [Covers Section 3.2, 3.3 in our textbook], or, lecture notes .
- Lecture 8. Kirkpatrick's Point Location. Lecture Notes.
- Exam 1: Tuesday, March 1, in class. [Note this does not really like up with the number of lectures, but material above this line will be on the midterm].
- Lecture 9. Trapezoidal Decomposition/Randomized Incremental Construction. Lecture Notes.
- Lecture 10. Properties of Delaunay triangulations Lecture Notes
- Lecture 11 Fortune's Algorithm for Computing Voronoi Dia]grams Lecture Notes,Fortunes Sweep Line Video, and step by step animation.
- Lecture 12 Relations between 2D Delaunay and 3D convex hulls, and 2D voronoi and 3D cones. Lecture Notes.
- Lecture 13 Incremental construction of Delaunay Triangulations Lecture Notes
- Lecture 14 Alpha Hulls and Farthest Point Voronoi Diagrams Lecture notes, the original alpha-hull paper, Paper about the "R" implementation of alpha-hulls, Lecture notes from a topology class, applet 1, Voronoi with additive weights
- MIDTERM 2
- Lecture 16.5 Duality and Line Arrangements [Chapter 8 of the textbook]. Some related lecture notes (second half of this link). web demo, my lecture notes
- Lecture 17. Zone Theorem and applications of arrangements.
- Lecture 18 K-D trees Lecture Notes. [Book, Chapter 5.1 -- 5.3]
- Lecture Pre-Thanksgiving Kinetic Algorithms. lecture notes (Not on final exam)
- Lecture 19 Orthogonal Range Trees and Fractional Cascading Lecture Notes. Also, here are alternative notes. This is also covered in [Book, Chapter 5.4 -- 5.6].
- Lecture 20 Nearest Neighbor Searching with KD trees and effects of dimension on algorithmic perforance. Lecture notes are a subset of these (slids 15--21)