Lecture: 3 hours
Prerequisite: Courses 175, 222A
Grading: Letter; homework (30%), project (50%), presentation (20%)
Mathematics of unstructured data. Algorithms for data structures such as Voronoi diagrams, oct-trees, and arrangements. Applications in computer graphics, concentrating on problems in three-dimensions. Offered in alternate years.
Provide enough background to allow students to use current results or software from computational geometry in their work or to begin pursuing research in the area.
Expanded Course Description:
Projects will be agreed upon with the instructor early in the quarter. Typically a project will be a survey of a few current research papers, but programming or original theory projects are also possible.
M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer-Verlag, 2000. This will be supplemented by recent research papers.
Instructors: N. Amenta and N. Max
Prepared by: N. Amenta (March 2004)
There is no significant overlap with other courses.