CS 677 - Computational Geometry

 

Credits: 3

 

Course 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.

 

Prereqs: CS 515 or consent of instructor.

 

Needed Skills

 

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

 

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.

 

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.

 

Examinations

 

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.

 

Grading

 

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.