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.
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:
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.
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.