Detailed schedule

Week 1:

Jan 24, 26

• Topics: Class intro. Warmup: Finding collinear points. Finding the closest pair of points.
• Resources:
  • collinear points: collinear.pdf ; ex-collinear.pdf
  • closest pair: closest.pdf; ex-closest.pdf
• Project: Project 0-setup ; Project 1-closest

Week 2:

Jan 30, Feb3

• Topics: Geometric primitives. OpenGL 1.x primer.
• Resources:
• Project: [work on project 1, due on Monday 2/6];

Week 3:

Feb 6-10

• Topics: Convex hulls in 2D, properties, algorithms (Gift wrapping, Quickhull, Graham scan, Andrew’s monotone chain, incremental) and lower bound.
• Resources: ex-hull.pdf
• Project: Project 2-hull2d

Week 4, 5:

Feb 13-24

• Topics: 2D space partitioning data structures (range trees and kd-trees) and range searching.
• Resources: ex-kdtrees.pdf
• Project: [work on project 2, due on Sunday 2/19]; Project 3-mondrian

Week 6, 7:

Feb 27-March 7

• Topics: Range trees - queries. Segment-segment intersection. Point-in-polygon tests and ray crossings. Art gallery problems, definition and properties. Fisk’s sufficiency proof.
• Resources: ex-rangetree3d.pdf
• Project: [work on project 3, due on Wed 3/1]; Project 4-guard

Week 8

• Topics: Line segment intersection and Bentley Ottman sweep
• Resources:
• Project: [work on Project 4, art gallery]

Week 9, 10

• Topics: Convex hulls in 3d: Definition, properties, algorithms (naive, gift-wrapping, incremental).
• Resources:
• Project: [work on Project 5, hull3d]

Week 10, 11:

• Topics: Polygon triangulation: proof of existence and naive algorithms. Triangulation by ear removal. Triangulating uni-monotone and monotone polygons. Triangulation via trapezoidation. An O(n lg n) algorithm via plane sweep to compute trapezoidation.
• Resources:
• Project: [work on project 5, hull 3d] [work on project 6, visibility graph]

Week 12, 13, 14:

• Topics: Motion planning
• Resources:
• Project: [work on project 6, visibility graph] [work on project 7, heuristical mp]