CPSC 516 Computational Geometry 2022W1

William Evans, ICCS X841, 822-0827, e-mail: will@cs.ubc.ca, home page: www.cs.ubc.ca/~will/,


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
Voronoi Diagrams scribe 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
Range Query scribe CGAA Chapter 5 & 14
RTIN extra
ε-nets and simplex range queries no scribe Zurich Appendix H
Haussler & Welzl, ε-nets and simplex range queries
ε-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 and planarity
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 Lovász Geometry and Graphs Chapter 3
Tutte How to Draw a Graph
Felsner Crash Course: Schnyder Woods and Applications

Probable Topics:

Homework 1 ( Solutions )
Homework 2 ( Solutions )
Homework 3 ( Solutions )

Area Description:

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.

University Policies:

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.