CSE 546: Computational Geometry

Spring 2009, on T,Th, 5:30-7:00, Cupples II, Room 217

No Textbook Required

Example Applications of Voronoi Diagrams and Delauney triangulations to a toy land use problem...

... not to be confused with the abstract, Paul Klee like work of Robert Delaunay.

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.

Office Hours: Robert Pless,   Thursday 4:30-5:30, Lopata 518

              Richard Speyer, Wednesday, 2-4, M&M lab, 5th floor
	      Lopata.

Sample Final pdf link, and solutions pdf link.

Approximate Lecture Notes. Lectures still to come are in green.

• Lecture 1, Intro to class, intro to convex hulls, slides. Reading for the lecture: here (ps).
• Lecture 2, More convex hull algorithms. Lower bound and relationship to sorting. Lecture will follow page 13-17 of: Dave Mount's Lecture Notes. applet link.
• Lecture 3. Optimal Convex Hull Algorithms lecture Notes, and Homework 1.
• Lecture 4. Line Segment intersection. First plane sweep algorithm. Use of heap and balanced binary tree. Touch on reduction from element uniqueness.Approximate lecture 4 notes, and slides applet.
• Lecture 5. Planar Subdivisions, Double connected edge lists. Euler's Theorem. Approximate lecture 5 notes.
• Lecture 6. Art Gallery Theorem, intro to triangulation Approximate lecture 6 notes
• Lecture 7. Monotone Partitioning + Monotone Polygon Triangulation == O(n log n) polygon triangulation. lecture notes
• Lecture 8. Kirkpatricks Point Location Notes, Homework 1 solution. Homework 2.
• Lecture 9. trapezoidal decomposition Notes, applet.
• Lecture 10 trapezoidal point location Notes.
• Lecture 11 Voronoi 1 Notes, and answer to question, how to convert trapezoidal map into actual point location query, because, eh, you have to add the edges in randomly, and doesn't that wreck any spatial structure you have?
• Lecture 12 Delaunay 1Notes
• Lecture 13 Relations between 2D Delaunay and 3D convex hulls, and 2D voronoi and 3D cones Notes.
• Homework 3
• Lecture 14 Fortunes Algorithm for Computing Voronoi DiagramsNotes.
• Lecture 15 Incremental construction of Delaunay TriangulationsNotes.
• Lecture 16. Alpha Hulls and Farthest Point Voronoi Diagrams Slides, Alpha Hull Applet.
• Lecture 17. K-D trees. Notes.
• Lecture 18. Orthogonal Range Trees and Fractional Cascading, Notes.
• Lecture 19. Duality and Line Arrangements 1 Notes, Applet.
• Lecture 21. Collision Detection Slides,
• Lecture 20. Kinetic Algorithms Slides, applet
• Lecture 21. Kinetic Algorithms, take 2 notes