CS 661 Geometric Algorithms
Syllabus

This syllabus outlines the schedule for the material in CS661 this semester. It is approximate and will vary, as the precise amount of material that can be covered with clarity in a given session is occasionally hard to predict. You may expect the dates of the exams to be as stated, Assignment submission may vary in form and timing, and will be discussed as we go, but should follow relatively closely the stated dates. Dates on the syllabus may be adjusted from time to time in class, and they will be updated online shortly thereafter.

Spring 2012
Week #, Mtg-Dates Topics Links Events
Week 1
Thu, Jan 19
Session 1
 Introduction
Applications, motivation
Mapping non-geometric problems into CG space
Defining the convex hull
 de Berg, Ch. 1
-
Week 2
Tue, Jan 24
Session 2
----------------
Thu, Jan 26
Session 3
 SimpleConvexHull and its analysis
Moving toward a better design
----------------
Graham's scan and its analysis
Proofs of correctness and complexity
 de Berg, Ch. 1
----------------
de Berg, Ch. 1
-
----------------
-
Week 3
Tue, Jan 31
Session 4
----------------
Thu, Feb 02
Session 5
 NO CLASS
----------------
Some computational geometry background/intuition
Primitives, intersections
Line/plane-sweep approach
 INSTRUCTOR OBLIGATION
----------------
Notes
-
----------------
-
Week 4
Tue, Feb 07
Session 6
----------------
Thu, Feb 09
Session 7
 Line segment intersection
Review of BSTs and height-balancing (AVL trees)
----------------
Line segment intersection and correctness/complexity proof
 de Berg, Ch. 2
Handout
----------------
de Berg, Ch. 2
-
----------------
Exercise One due
Week 5
Tue, Feb 14
Session 8
----------------
Thu, Feb 16
Session 9
 Guarding and triangulations
Monotone partitioning
----------------
Monotone partitioning
Triangulating a monotone polygon
 de Berg, Ch. 3
----------------
de Berg, Ch. 3
-
----------------
Exercise Two due
Week 6
Tue, Feb 21
Session 10
----------------
Thu, Feb 23
Session 11
 Open discussion; trace of MakeMonotone
----------------
1-D Range Searching
 de Berg, Ch. 3
----------------
de Berg, Ch. 4
-
----------------
-
Week 7
Tue, Feb 28
Session 12
----------------
Thu, Mar 01
Session 13
 EXAM I
----------------
Range searching and kD-trees
-
----------------
de Berg, Ch. 5
-
----------------
-
Week 8
Tue, Mar 06
Session 14
----------------
Thu, Mar 08
Session 15
 Range Trees
----------------
Range Trees
 de Berg, Ch. 5
----------------
de Berg, Ch. 5
-
----------------
-
Week 9
Tue, Mar 13
Session 16
----------------
Thu, Mar 15
Session 17
 Trace of construction and query
----------------
Point Location and Trapezoidal Maps
 de Berg, Ch. 5
----------------
de Berg, Ch. 6
-
----------------
-
Week 10
Tue, Mar 20
Session 18
----------------
Thu, Mar 22
Session 19
 Point Location and Trapezoidal Maps
----------------
Randomized Incremental Algorithm for Point Location
-
de Berg, Ch. 6
----------------
de Berg, Ch. 6
-
----------------
-
Spring Break
Tue, Mar 27
----------------
Thu, Mar 29
*
----------------
*
*
----------------
*
*
----------------
*
Week 11
Tue, Apr 03
Session 20
----------------
Thu, Apr 05
Session 21
 Voronoi diagrams: the post office problem
----------------
EXAM II
 de Berg, Ch. 7
----------------
EXAM II
-
----------------
EXAM II
Week 12
Tue, Apr 10
Session 22
----------------
Thu, Apr 12
Session 23
 Definition of Voronoi diagram and properties
----------------
Computing the Voronoi diagram
 de Berg, Ch. 7
----------------
de Berg, Ch. 7
-
----------------
-
Week 13
Tue, Apr 17
Session 24
----------------
Thu, Apr 19
Session 25
 Computing the Voronoi diagram
----------------
Computing the Voronoi diagram
 de Berg, Ch. 7
----------------
de Berg, Ch. 7
-
----------------
-
Week 14
Tue, Apr 24
Session 26
----------------
Thu, Apr 26
Session 27
 Tracing an example
----------------
Delaunay triangulations
 de Berg, Ch. 7
----------------
de Berg, Ch. 8
-
----------------
-
Week 15
Tue, May 01
Session 28
----------------
Thu, May 03
Session 29
 Delaunay triangulations
----------------
Open Discussion
Schedule Buffer
 de Berg, Ch. 8
----------------
-
-
----------------
-
Week 16
Tue, May 08
Session 29
-------------
Thu, May 10
 Open Discussion
-------------
FINAL EXAM
-
-------------
3:30 - 5:30pm
-


-------------
(FINAL IS IN SAME ROOM)

------------>
-


Learning Objective & Outcomes

[Back to CS547 Homepage]