Computer Science

ECS 226 Computational Geometry

ECS 226 COMPUTATIONAL GEOMETRY (4) III

Lecture: 3 hours

Prerequisite: Courses 175, 222A

Grading: Letter; homework (30%), project (50%), presentation (20%)

Catalog Description:
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.

Goals:
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:

  1. Introduction: polygon trapezoidation
  2. Geometry of convex hull, Voronoi diagram and Delaunay triangulation
  3. Algorithms for their construction
  4. Arrangements of curves, surfaces and lines
  5. Theory of oct-trees, kd-trees and BSP trees
  6. Applications
  7. Special topics

Project:
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.

Textbook:
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)

Overlap Statement:
There is no significant overlap with other courses.

Revised: 12/92

border