## Clarkson University

## CS 446 / CS 556: Computational Geometry

## Course Syllabus -- Fall 2004

**Professor: **William Hesse

**Office:** Science Center
383

**Phone:** 268-2387

**Email:** whesse@clarkson.edu
**Office hours:**

Monday |
9:00-11:00 |

Tuesday |
12:00-2:00 |

Wednesday |
2:00-3:00 |

Friday |
10:00-12:00 |

Or by appointment |

**Course Objectives: **

- Students will learn common data structures for representing and searching
2-dimensional and 3-dimensional geometric objects.
- Students will learn important algorithms and new algorithmic techniques
for solving geometric computational problems.
- Graduate 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.

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

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

**SYLLABUS **

CHAPTER |
TOPIC |

1 |
Polygon Triangulation |

2 |
Polygon Partitioning |

3 |
2D Convex Hulls |

Not in book |
Curves and Curved Surfaces |

4 |
3D Convex Hulls |

5 |
Voronoi Diagrams |

7 |
Search and Intersection |

8 |
Motion Planning |

**GRADING **

- Assignments 50%
- Class Participation & Quizzes 20%
- Final Project 30%

**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 credited
in the documentation.
**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.

Author: William Hesse

Last
Modified: Sep 10, 2004