Professor: Nina Amenta

Class meets:Tu,Th 10:30-11:50, 90 SocSci

Office Hour:Wds 4pm-5pm.
I also have undergraduate advising hours on Th 4-6pm, and I am happy to talk to you then if there are no undergraduates waiting.

Textbook: Computational Geometry: Algorithms and Applications by Mark de Berg, Marc van Kreveld, Mark Overmars and Otfried Schwarzkopf, 2nd Edition.
ISBN: 3-540-65620-0
The text will be supplemented with research papers and occasional handouts. Prerequisites: Consent of instructor.

Introduction

This year one special focus will be the complexity of higher-dimensional Delaunay triangulations; other special topics will depend on the interests of the class.

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: 2D BSP trees.
• 2D Delaunay triangulations.
• Convex hulls in R^d and their construction.
• Relations between Delaunay triangulations and convex hulls.
• Low-dimensional linear programming.
• Kd-trees, Oct-trees, nearest-neighbor searching and range searching.

• Delaunay triangulations of points distributed on surfaces.
• Molecular surface constructions.

Format

We will read chapters in the textbook as well as supplementary material that will be distributed in class. 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 you do the reading and that we can have a meaningful discussion in class.

There will also be some homework problems reviewing the important concepts. These will give you practice in algorithm design and analysis. These homework problems, like the reading questions, will be due in class.

Each student will have to give a half-hour presentation some time during the quarter; we will make a schedule in the first week. The presentation will usually cover a paper or other reading supplementing the material that the whole class reads.

Each student will pick a project in consultation with the instructor. The project must involve reading a reasonably deep paper which uses computational geometry; aside from that I am pretty flexible. It may consist of a written survey of a few papers (or even just one, if it is really hard), implementation, experiments with computational geometry software, or developing new theory. Ideally the project should be the first steps towards a publishable result. You are encouraged to find something related to your existing research or your ultimate research goals.

Grading

Assignments

Links

• Paul Chew's Voronoi/Delaunay applet