Lecutre: Tues-Th, 12:10p-1:30pm, 127 Wellman Office Hour:T 4-5pm, Th 4:30-5:30 3015 Kemper Hall I also have undergraduate advising hours on Wds 3-5pm, 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 or 3rd Edition. ISBN: 3-540-65620-0 The text will be supplemented with research papers and occasional handouts. The book is available as pdf through the UC Davis library! Thanks to Taeho for pointing this out. The link works from computers on campus, or via these tricks, which Jim pointed out.. Prerequisites: Consent of instructor.

Introduction

This year a theme will be "reasonable" models of input distributions; that is, under what input distributions will algorithms perform better than in the worst case? Are these distributions likely in practice, and how can we argue this? Oher special focii 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: BSP trees.
• 2D Delaunay triangulations.
• Convex hulls in R^d, their construction, and relation to Delaunay triangulation.
• Kd-trees, nearest-neighbor searching and range searching.
• Octrees: three tricks.

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 second week. The presentation will usually cover a paper or other reading supplementing the material that the whole class reads.

Each student will work on a project, chosen in consultation with the instructor. I will suggest some projects that several people can share, and students who have ideas of their own are encouraged to bring them up. The project must involve reading a reasonably deep paper which uses computational geometry; aside from that I am pretty flexible. Something related to your existing research or your ultimate research goals is good. Ideally the project should be the first steps towards a publishable result.

Grading

Assignments

Resources

• Some computataional geometry software you might use for projects.
• List of Open Problems in Computational Geometry