CS 677 - Computational Geometry

Bulletin Description

Review of basic algorithms and discussion of active research topics in the design and analysis of efficient algorithms and data structures for geometric problems with applications in computer graphics, pattern matching, manufacturing, robotics, facility location, and geographic information systems. Practical issues pertaining to efficient and accurate implementations, and related to libraries of geometric data structures and algorithms.


CS 515 or consent of instructor.

Expected Preparation

Familiarity with basic data structures and algorithms. Students should be adept in programming in a modern object-oriented language.

Student Learning Outcomes

A successful student will be able to use and will understand:

· Classic and recent geometric algorithms;

· Useful geometric data structures (segment trees, trapezoidal decomposition, BSP trees, kd-trees);

· Methods for designing efficient geometric algorithms (sweeping line, randomization, parametric search);

· Main application areas for geometric algorithms;

· Issues related to implementation of geometric algorithms (numerical errors versus topological and geometric consistency);

· Current literature in computational geometry.

Syllabus Information

Week by Week Course Outline:

This is a sample outline. Exact outline for this course will be determined by the instructor offering the course.

Weeks Topics
1-5 Classic problems and methods in computational geometry
6-7 More advanced techniques: parametric search, randomization.
8-11 Selected research topics in computational geometry
12-15 Selected application areas: one or two selected from computer graphics, manufacturing, robotics, GIS, geometric optimization.


Exact details about examinations in this course will be determined by the instructor offering the course. Typically there will be one in-class examinations during the semester and a two-hour final examination. Specific details will be made available in the syllabus at the start of each semester in which the course is offered.


A student's grade will be determined by a weighted average of homework assignments, programming exercises, projects, in-class examination, and the final examination. The faculty offering the course will make the details available at the start of the course. A typical weighting is:

Homework Assignments 30%
Project & Programs 40%
Examinations 30%

Possible Textbooks:

Herbert Edelsbrunner,
Algorithms in Combinatorial Geometry,
Springer Verlag, 1987.