Class Times: Tu/Th 10:30-11:50AM

Location: Seelye 212

Office Hours: Schedule & Office Hours

Prerequisites:  MTH 153 (Discrete) and CSC 112 (CS-2).  Because this course is only offered every other year, those with a strong enough background in mathematics may take it without having yet taken Discrete, by permission of instructor.  Sufficiently advanced math majors who have not taken CSC 112 may take the course by permission of instructor.

Relation to CS Major:  Satisfies the "Theory" requirement:  either Algorithms (CSC 252) or Programming Languages (CSC280) or Computational Geometry (CSC274).  [To use this to satisfy the CS requirement, you must have previously taken CSC 112.]

Textbook (required): Computational Geometry in C (2nd ed.) by Joseph O'Rourke.  My other books, available in the library, could be useful resources.
 

Course Description (informal):

The focus of this course is the design and analysis of geometric algorithms.  This field sits at the nexus of computer science and discrete geometry, with ties to many application areas, including computer graphics, robotics, GIS (Geographic Information Systems), engineering, and manufacturing.  The topics can be vieTues as a subfield of data structure and algorithm design, but it has developed into a specialty of its own.  We will cover the major geometrical structures---triangulations, convex hulls, Voronoi diagrams, arrangements of lines; the major techniques---plane sweep, reduction to combinatorics, lifting to a higher dimension; and the major application areas listed above.

Assignments:  Students will have weekly assignments, involving both theory (mathematics, or paper-and-pencil design of algorithms), and implementations (either de novo programs in C or C++, or extensions of existing software, either mine or CGAL).  Those with strengths in either direction may emphasis one or the other. Assignments will be distributed by Thursday's class, and are due in one week on the following Thursday.

Collaborations: Students may collaborate with each other on all assignments except for A5, and on the project. I will expect somewhat more work and quality from n students working together than from a student working on her own.

Midterm:  There is no midterm, but rather just a two-week assignment near Fall Break. There are three distinctions between this the other assignments: (1) This is the only assignment on which you may not collaborate with other students; (2) You have two weeks rather than one week for this assignment; (3) It will count as two assignments.

Final/Project: Students will have an option of doing a project, or taking a final, take-home exam. Projects include a brief, preliminary class presentation. I hope most students will chose to do a project.

Grading Weights:  Assignments: 75% (including the midterm assignment); Project or Final Exam: 25%.

 

Syllabus (detailed):