ECS 226: Computational Geometry

Subject
ECS 226
Title
Computational Geometry
Status
Active
Units
4.0
Effective Term
2016 Spring Quarter
Learning Activities
Lecture - 3.0 hours
Discussion - 1.0 hours
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.
Prerequisites
ECS 175; ECS 222A
Enrollment Restrictions
Pass One and Pass Two open to Graduate Students in Computer Science only.

Summary of Course Content
I. Introduction: polygon trapezoidation

II. Geometry of convex hull, Voronoi diagram and Delaunay triangulation

III. Algorithms for their construction

IV. Arrangements of curves, surfaces and lines

V. Theory of oct-trees, kd-trees and BSP trees

VI. Applications

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



Illustrative Reading
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.



Potential Course Overlap
There is no significant overlap with other courses.

Course Category

Graduate