T Th 11.00-12.30 DMP 201
|Polygon Triangulation||no scribe||
Zurich Chapter 3
CGAA Chapter 3
|Guarding, Trapezoidization||no scribe||CGTAA Chapter 3|
|Best Polygon Partition||scribe||O'Rourke Chapter 2.4|
|2D Convex Hull||scribe||O'Rourke Chapter 3|
|Optimal 2D Convex Hull||scribe||
Zurich Chapter 4
Kirkpatrick & Seidel The Ultimate Planar Convex Hull Algorithm?
Chan Optimal Output-sensitive Convex Hull Algorithms in Two and Three Dimensions
Erickson's notes on Algebraic Decision Trees
|3D Polyhedra||no scribe||
O'Rourke Chapter 4
|3D Convex Hulls||scribe||
O'Rourke Chapter 4
Chan's 3D convex hull kinetic divide and conquer (with code)
|More than 3D Convex Hulls||no scribe||Seidel Small-Dimensional Linear Programming and Convex Hulls Made Easy|
|More than 3D Convex Hulls - Part 2||scribe||Seidel Backwards Analysis of Randomized Geometric Algorithms|
CGAA Ch. 7
Zurich Ch. 7
|Delaunay Triangulations||no scribe||
CGAA Ch. 9
Zurich Ch. 7
|Randomized Incremental Delaunay||scribe||
Seidel Small-Dimensional Linear Programming and Convex Hulls Made Easy
Mount Lecture 13
|Connect the dots with Crust||scribe||
Amenta, Bern, Eppstein
The Crust and the β-Skeleton: Combinatorial Curve Reconstruction
|Line Arrangements and Duality||no scribe||CGAA Chapter 8|
|Zone Theorem||CGAA Chapter 8|
|Crossing Number, Ham Sandwich, 3SUM||scribe||Zurich Chapters 8 & 10|
|Point Location||scribe||CGAA Chapter 6|
CGAA Chapter 5 & 14
|ε-nets and simplex range queries||no scribe||
Zurich Appendix H
Haussler & Welzl,
|ε-nets continued||no scribe||Matoušek Lectures on Discrete Geometry Chapter 10|
|ε-nets and almost optimal hitting sets||no scribe||Brönnimann & Goodrich Almost optimal set covers in finite VC-dimension|
|Planar Drawing and Canonical Orders||no scribe||
de Fraysseix & Ossona de Mendez Trémaux trees
Brandes The Left-Right Planarity Test
de Fraysseix, Pach & Pollack How to draw a planar graph of a grid
|Schnyder Woods and Contact Representation of Graphs||no scribe||Felsner Crash Course: Schnyder Woods and Applications|
|Tutte Embeddings||no scribe||
and Graphs Chapter 3
Tutte How to Draw a Graph
Felsner Crash Course: Schnyder Woods and Applications
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.
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.