ECS 226  Computational Geometry
CRN #43770

Lecutre: TuesTh, 1:40p3:00pm, 1342 Storer
Office Hours:M 23 pm, Th 3:304: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: 3540656200
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.

Introduction
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:
 Warm up: BSP trees.
 2D Delaunay triangulations.
 Convex hulls in R^{d}, their construction, and relation to
Delaunay triangulation.
 Octrees: three tricks.
 Kdtrees, nearestneighbor searching and range searching.
 Other topics depending on the interests of the class.
Format
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 shortanswer 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 openended 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.
Grading
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
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?
Resources