T Th 11.00-12.30 DMP 201
Computational Geometry is an area of computer science that studies problems concerning geometric objects. For example, how many cameras are required so that every point in an art gallery is seen by at least one camera, and where should they be placed? Or, what is the closest gas station to your current location?
We will explore computationally efficient solutions to these problems and cases where efficient solutions are highly unlikely.
The course has no official textbook. The following books and notes, however, are excellent resources to help understand the material we will cover. Many thanks to Anna Lubiw at University of Waterloo for sharing her class notes with me.
| [CGAA] |
Computational Geometry: Algorithms and Applications, (third edition) by
M. de Berg, O. Cheong,
M. van Kreveld, M. Overmars, Springer, 2008. |
| [Mount] | CMSC 754 Computational Geometry Lecture Notes by D. Mount, 2021. |
| [Zurich] | Geometry: Combinatorics & Algorithms Lecture Notes by L. Barba, B. Gärtner, M. Hoffmann, E. Welzl, 2019. |
| [O'Rourke] | Computational Geometry in C by J. O'Rourke, 1994. |
| [Handbook] | Handbook of Discrete and Computational Geometry (3rd edition), edited by Goodman, O'Rourke, Toth, CRC Press, 2017. |
The course is intended for students with a basic understanding of algorithms, data structures, and graphs.
Students will be required to do an in class presentation of an approved project of their choice. The project might be, for example, an implementation, a literature exploration, or a solution to a theoretical problem. Please see the instructor as early as possible to discuss possibilities. The project and presentation will contribute 50% to the final grade. In addition, there will be occasional homework exercises with some required reading (25%), and class participation (25%), which includes participating in class and typesetting (or webpaging) notes for one or two lectures so that they may be distributed to the rest of the class.
UBC provides resources to support student learning and to maintain healthy lifestyles but recognizes that sometimes crises arise and so there are additional resources to access including those for survivors of sexual violence. UBC values respect for the person and ideas of all members of the academic community. Harassment and discrimination are not tolerated nor is suppression of academic freedom. UBC provides appropriate accommodation for students with disabilities and for religious observances. UBC values academic honesty and students are expected to acknowledge the ideas generated by others and to uphold the highest academic standards in all of their actions. Details of the policies and how to access support are available on the UBC Senate website.
UBC's Point Grey Campus is located on the traditional, ancestral, and unceded territory of the xwməθkwəy̓əm (Musqueam) people. The land it is situated on has always been a place of learning for the Musqueam people, who for millennia have passed on their culture, history, and traditions from one generation to the next on this site.