Prerequisites

The formal requirements are 600.226 Data Structures. The student should also have a minimal amount of ``mathematical maturity'', and it is recommended that the student have had 600.363 Introduction to Algorithms or 600.463 Algorithms I (but this is not required).

Course Summary

The goal of the course is teach the fundamental paradigms for designing efficient algorithms dealing with collections of geometric objects (such as points, lines, line segments, planes, etc.). The course topics include the following:

• Convex hulls
• Proximity problems and Voronoi diagrams
• Geometric searching and planar point location
• Planar decompositions and triangulations
• Intersection and arrangement problems
• Visibility and envelope problems
• Randomization in geometric algorithms

Grading

The course grade is determined by the total number of points earned by the student during the semester. There are 1000 points possible, distributed as follows:

400 pts. Homework assignments

200 pts. Paper review or Programming Project

150 pts. Midterm exam

250 pts. Final

Late policy: 10% off for each day late. No credit if more than 2 days late.

Text

See the course web site (http://www.cgc.cs.jhu.edu/~goodrich/teach/geom/ ) for an on-line text, which will be ``under construction'' throught the semester.