Computational geometry studies the design, analysis, and implementation of algorithms and data structures for geometric problems. These problems arise in a wide range of areas, including CAD/CAM, robotics, computer graphics, molecular biology, GIS, spatial databases, sensor networks, and machine learning. In addition to the tools developed in computer science, the study of geometric algorithms also requires ideas from various mathematical disciplines, e.g., combinatorics, topology, algebra, and differential geometry. This close interaction between various mathematical and practical areas has had a beneficial impact on both basic and applied research in computational geometry.
The goal of this course is to provide an overview of the techniques developed in computational geometry as well as some of its application areas. The topics covered in the course will include:
The main textbook used in the course:
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, 2nd or 3rd Edition Springer, 2000/2008. The book is not available in the Duke Textbook Store. It can be ordered from Amazon but there is a 4-6 week wait.
Assignments: 30% weight
Four assignments will be given during the semester, which each student has to complete individually.
Final Exam: 30% weight
A take-home exam will be given at the end of the semester. The exact dates will be discussed in the class.
Research Project: 40% weight
The intention is to produce a work of publishable or near-publishable quality. It will consist of a comprehensive survey on a topic plus new research work.