ECS 226 - Computational Geometry

CRN #43770

Lecutre: Tues-Th, 1:40p-3:00pm, 1342 Storer

Office Hours:M 2-3 pm, Th 3:30-4:30 3029 Kemper Hall

Textbook: Computational Geometry: Algorithms and Applications by Mark de Berg, Marc van Kreveld, Mark Overmars and Otfried Schwarzkopf, 2nd or 3rd Edition.
ISBN: 3-540-65620-0
The text will be supplemented with research papers and occasional handouts.
The book is available electronically through the UC Davis library! Use the link works from computers on campus, or first connect from off campus.

Prerequisites: Consent of instructor; you should have a good grounding in undergraduate algorithms.


In this class we study the mathematics of unstructured sets of points, planes, triangles or other objects, algorithms for spatial data structures, and applications in computer graphics, visualization, and other areas like molecular modeling or databases.

The goal is to 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.

Topics will include:


We will work on research skills such as reading, writing and speaking as well as on concepts and analysis.

Class meetings will focus on discussion of the reading material, rather than lectures. There will be a reading assignment due before most class meetings, either from the textbook or from supplementary material. For all the readings, there will be short-answer questions which have to be answered in writing, in class on the day that the reading is due. This is to ensure that everyone does the reading, so that we can have meaningful class discussions.

There will be two problem sets, to provide practice in algorithm design and analysis, as well as writing. These homework problems, like the reading questions, will be due in class.

There will be a small, more open-ended project in the later half of the quarter. I hope that students will work on these in small groups. Each group will make a presentation at the end of the quarter.


Grades will be determined using this formula (approximately):

Reading questions 15%
Homework 35%
Project and pesentation 35%
Attendance, preparation and participation 15%

Class Schedule

Readings and reading questions.


Homework 1 Homework 2 - extra credit

While you may discuss the homework with each other, you must a) write up your own solutions, in your own words, and b) report, in your solutions, who you discussed the problems with and what other sources (papers, Web, books, etc) you used to arrive at the solution. This is to ensure that you do understand the solutions.

Applications Projects

Here are my project ideas; what are yours?