EECS 395/495 - Computational Geometry
CATALOG DESCRIPTION: After a brief introduction to numerical computation issues, the course will continue with a sequence of canonical problem settings (e.g., Intersections; Arrangements/Duality), mostly focusing on the combinatorial aspects of the algorithms and the impact of the data structures. Each part will be casted in respective applications settings (GIS; Motion Planning; etc). The last part of the course will present several potpourri-like topics, e.g., Skeletons/Medial Axis; Davenport-Shinzel sequences.
REQUIRED TEXTBOOKS: Computational Geometry, Algorithms and Applications, By M. de Berg, M. Van Kreveld, M. Overmars and O. Schwarzkopf (Springer).
COURSE COORDINATORS: Prof. Goce Trajcevski
COURSE OBJECTIVES: The main goals of these course can be categorized as follows: (1) It will expose the students to the fundamental ideas of the field of computational geometry; (2) Through discussing application scenarios with different topics, it should provide an insight into how one can recognize the inherent geometric properties of a particular application domain; (3) Through the programming projects, it will enable the students to combine existing libraries for the purpose of developing efficient implementations of various algorithmic solutions. In addition, since part of the course will consist of reading assigned papers on contemporary research topics, it will help the students develop a geometric intuition when approaching research problems.
After finishing the course, the students should be comfortable with reading and understanding of the vast body or research literature that is founded on certain computational geometry results. They will also be able to reason about inherent trade-offs when selecting particular data structures representing the geometric features of a given domain, and will be comfortable in developing their own implementations, while capitalizing on the existing libraries.
PREREQUISITES: EECS 311 (or consent of the instructor)
ASSIGNMENTS: The course will have two homeworks, two projects, a midterm and an in-class presentation. There will be no final exam, however, the students will have to submit the reports for the 2nd project and, if needed, do a demo presentation throughout the finals week.