Home Page for CMSC 754 (Computational Geometry)

Instructor: Samir Khuller Office: AVW 3217. Office phone: 405--6765. E-mail: samir@cs.umd.edu.

Office Hours: Tuesday 2:00--3:00, and Friday 11:00--12:00. If you cannot make these hours, please make an appointment to see me at a different time.


Wed: 10--11

Thu: 3--5

Fri: 11--12 and 3:30 --4:30

Teaching Assistant: Michael Murphy Office: AVW 3228. Office phone: 405--2717. E-mail: murphy@cs.umd.edu.

Office Hours: Tuesday 10:00--11:30, and Thursday 4:30--5:30. If you cannot make these hours, please make an appointment to see Michael at a different time.

I hope to maintain this page and update it every week this semester. I will place all homeworks as well as solutions to homeworks here. If you have any trouble accessing them, please let me know.

Class Time: Monday and Wednesday 11.00--12.15, Room: CLB 0109.

Course Overview: Introduction to algorithms and data structures for computational problems in discrete geometry (for points, lines, and polygons) primarily in 2 and 3 dimensions. Topics include triangulations and planar subdivisions, geometric search and intersection, convex hulls, Voronoi diagrams, Delaunay triangulations, line arrangements, visibility, and motion planning.

Text: We will use more than one book. The first one (O'Rourke) will be the main text for the course. We will also use the second one from time to time (Preparata and Shamos). The other two books are mostly for your entertainment.

Suggested Syllabus: This is only a rough outline -- we may do things in a different order.

Grading: Final grades will be based on homework assignments, the midterm exam, and the final exam. The relative weights of these will be 30% for the homework total, 30% for the midterm, and 40% for the final exam.

REMINDER: Midterm on March 11. Skinner 0200 11:00-12:15.

REMINDER: Final on May 11 (sat). AVW 1112/1152 9:30-12:00.

Class Handout

Handout on Ultimate Convex Hull Alg

Handout on Randomized Incremental Construction of Convex Hull's

Handout on Applications of Geometric Duality

Handout on Davenport-Schinzel Sequences

Handout on Visibility Graphs



Other Interesting Stuff:

Computational Geometry Home Page

Computational Geometry Talk at Johns Hopkins on Fri 23rd Feb.

Computational Geometry Day at NYU, New York on Fri 26th Apr.

Computational Geometry Job

Application Challenges to Computational Geometry