CSE555/AMS545 Computational Geometry Spring 2012

Time and Location
Instructors
 Announcements

Course Description: This course will cover fundamental geometric algorithm design and analysis.  Topics include: arrangments, point line duality, convex hull, linear programming, Voronoi diagram, Delaunay triangulation, visibility graph, point location, range search, etc.

Textbook
  1. [CG] Computational Geometry: Algorithms and Applications, 3rd Edition, Mark de Berg, M. van Krefeld, M. Overmars, O. Schwarzkopf, Springer, 2008. 
  2. [DCG] Discrete and Computational Geometry, Satyan L. Devadoss, Joseph O'Rourke, Princeton University Press, 2011.
  3. [DM] Lecture notes by Professor David Mount.
Grading rules
 Syllabus
Date Topics Reading Materials Homework, projects
1/24 Convex hull, incremental algorithm Big-O notation (courtesy to Michael Bender)
Geometry primitives ([DM] lecture 2)
Convex hull  
  • [CG] Chap 1.1
  • [DCG] Chap 2
  • [DM] lecture 3
1/26 Convex hull, divide and conquer, Jarvis' march, Chan's algorithm. Homework 1 out.
1/31 Arrangements
  • [CG] Chap 8.3
  • [DM] lecture 15
2/2 Sweeping line algorithm for line segments
Zone theorem
Incremental construction for arrangement of lines
  • [CG] Chap 2
  • [DM] lecture 7
2/7 Point line duality
Half plane intersection
Upper/lower envelope
  • [CG] Chap 8.2
2/9 LP 
  • [CG] Chap 4
 Homework 1 due.
Homework 2 out.
2/14 Faculty candidate talk
2/16 LP (randomized incremental construction)
Voronoi diagram
  • [CG] Chap 4
  • [CG] Chap 7
  • [DM] Lecture 11
2/21 Faculty candidate talk
2/23 Fortune's algorithm for Voronoi diagram
  • [CG] Chap 7
  • [DM] Lecture 11
 Homework 2 due.
2/28 Delaunay triangulation
  • [CG] Chap 9
  • [DM] Lecture 13
3/1 Flip, lifting map
  • [CG] Chap 9, 10
  • [DM] Lecture 13
 Homework 3 out.
3/6 Incremental construction
  • [CG] Chap 9, 10
  • [DM] Lecture 13
3/8 Randomized Incremental Construction
  • [CG] Chap 10
  • [DM] Lecture 13
3/13
3/15 Midterm in class (open book open notes)
3/20 Triangulation of a simple polygon
  • [CG] Chap 3
  • [DM] Lecture 6
3/22 Art Gallary Problem
Shortest path in a simple polygon
  • [CG] Chap 3
3/23 Makeup lecture: shortest path in a simple polygon Notes posted on blackboard.
4/10 kd tree, range tree
  • [CG] Chap 5
4/11 Makeup lecture: fractional cascading, interval tree
  • [CG] Chap 5, 10
 Homework 4 out.
4/19 Interval tree, priority tree
  • [CG] Chap 10
4/20 Makeup lecture: segment tree
  • [CG] Chap 10
4/24 Point location
  • [CG] Chap 6
4/26 Well separated pair decomposition
  • [DM] lecture 19, 20
5/1 Well separated pair decomposition
  • [DM] lecture 19, 20
5/3 Student presentation
Final