**Office hours:**

Monday | 1-2, 4-5 |

Tuesday | 11-12 |

Wednesday | 2-3 |

Thursday | 12-1 |

Friday | 10-11, 1:30-2:30 |

Or by appointment |

**Course Website: **www.clarkson.edu/class/cs446

**Course Objectives: **

- Students will learn common data structures for representing and manipulating 2-dimensional and 3-dimensional geometric objects.
- Students will learn important algorithms and new algorithmic techniques for solving geometric computational problems.
- CS 546 students will read papers from the computational geometry research literature and gain an appreciation for the current state of research in this area.
- Students will implement a major project that solves an interesting problem in computational geometry, which will require them to apply the course material in innovative ways.
- Implementations will visually portray the actions and results of geometric algorithms, using graphics and animation techniques.
- Students will learn how to use the OpenGL library to display and animate 2D and 3D objects.

**Textbook: **"Computational Geometry in C, 2nd Ed.",

by Joseph
O'Rourke. Published by Cambridge University Press.

**SYLLABUS **

CHAPTER | TOPIC |

Not in book |
Points, Vectors, Angles, and Inner Product |

1 | Polygon Triangulation |

2 | Polygon Partitioning |

Not in book |
OpenGL Programming |

3 | 2D Convex Hulls |

Not in book |
Curves and Curved Surfaces |

4 | 3D Convex Hulls |

Not in book |
3D OpenGL Programming |

5 | Voronoi Diagrams |

7 | Search and Intersection |

8 | Motion Planning |

**GRADING **

- Assignments 40%
- Class Participation & Quizzes 20%
- Final Project 20%
- Final Exam 20%

**Assignments: **The assignments will be programming projects, to be
completed individually. Reasonable amounts of help from fellow students and the
instructor are acceptable, and should be acknowledged in the documented code.

**Final Project:** The final project will be a programming project,
solving a problem to be decided on by the student and approved by the
instructor. Joint projects will be approved if the implementation can be split
into well-defined, separately testable parts, with each part being the
responsibility of one student.

**Late Policy **Late work will be penalized 20% per week. The final
project must be submitted by the last day of classes. No work submitted after
the end of the final exam period will be considered in computing the final grade
in the course.

**Academic integrity: **Assignments may be discussed with other students.
However, do not look at other students' solutions until you have solved the
problem yourself. You can give help to other students, but you may not just tell
them the answer.

Feel free to discuss the assignments and strategies for solving them (algorithms), but write the code yourself. You may not show another student your code for the purpose of helping them, but only if you are getting their help in debugging your code.

Author: William Hesse

Last
Modified: Aug 26, 2006