ECS 226 - Computational Geometry
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.
The text will be supplemented with research papers and occasional
The book is available electronically through the
UC Davis library!
Use the link works from
computers on campus,
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
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 Rd, their construction, and relation to
- Octrees: three tricks.
- Kd-trees, nearest-neighbor searching and range searching.
- Other topics depending on the interests of the class.
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
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%
Project and pesentation 35%
Attendance, preparation and participation 15%
Readings and reading questions.
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.
Here are my
project ideas; what are yours?