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.
Date  Topics  Reading Materials  Homework, projects 
1/24  Convex hull, incremental algorithm  BigO notation
(courtesy to Michael Bender) Geometry primitives ([DM] lecture 2) Convex hull


1/26  Convex hull, divide and conquer, Jarvis' march, Chan's algorithm. 

Homework 1 out. 
1/31  Arrangements 


2/2  Sweeping line algorithm for line
segments Zone theorem Incremental construction for arrangement of lines 


2/7  Point line duality Half plane intersection Upper/lower envelope 


2/9  LP 

Homework 1 due. Homework 2 out. 
2/14  Faculty
candidate talk 

2/16  LP
(randomized incremental construction) Voronoi diagram 


2/21  Faculty candidate talk  
2/23  Fortune's algorithm for Voronoi diagram 

Homework 2 due. 
2/28  Delaunay triangulation 


3/1  Flip, lifting map 

Homework 3 out. 
3/6  Incremental construction 


3/8  Randomized Incremental Construction 


3/13  
3/15  Midterm in class (open book open notes)  
3/20  Triangulation of a simple polygon 


3/22  Art Gallary Problem Shortest path in a simple polygon 


3/23  Makeup lecture: shortest path in a simple polygon  Notes posted on blackboard.  
4/10  kd tree, range tree 


4/11  Makeup lecture: fractional cascading, interval tree 

Homework 4 out. 
4/19  Interval tree, priority tree 


4/20  Makeup lecture: segment tree 


4/24  Point location 


4/26  Well separated pair decomposition 


5/1  Well separated pair decomposition 


5/3  Student presentation  
Final 