CS 164 Computational Geometry

Syllabus, Overview, and Schedule

Winter 2023

Michael T. Goodrich

Course notes and lecture slides: https://www.ics.uci.edu/~goodrich/teach/geom/notes/

Lecture videos: Please visit the Yuja link for this course.

Course description. Algorithms and data structures for geometric computation and graphics programming. Fundamental problems of computational geometry such as convex hulls, Voronoi diagrams, Delaunay triangulations, polygon partitioning, arrangements, geometric searching, hidden surface elimination, motion planning.
Coursework. Coursework will consist of weekly homeworks and quizzes, as well as two midterm exams and final exam. The overall grade will be determined 20% from quizzes, 20% from each midterm, 20% from the final, and 20% from the homeworks. The lowest quiz score will be dropped in computing the overall quiz grade. Group work on homeworks is permitted, but each student must list his or her collaborators in writing for each problem. If a student turns in a solution without listing the others who helped produce this solution, this act will be considered cheating (for it is plagiarism). Late homework assignments will not be accepted, but for the overall total homework score, the lowest homework score will be dropped.
Quiz/Exam policy. Quiz and exam performance must be 100% individual effort; no collaboration is allowed on quizzes or exams. Any collaboration or copying on quizzes or exams will be considered cheating. In addition to the procedures of the ICS Cheating Policy, students caught cheating on quizzes will be given a failing grade for the quiz/exam and may be given a failing grade for the course.
Laptop policy [in-class only]. Laptops may be brought to class, but should remain closed during in-class lectures and exams. Here's one reason why. Here is another.
Textbook. de Berg, Cheong, van Kreveld, and Overmars, Computational Geometry: Algorithms and Applications, Springer, 2008, 3rd edition.

Schedule

Week 1:

Introduction. Convex hulls.
Reading: Chapter 1.

Week 2:

Line segment intersections. Doubly-connected edge list. Boolean operations.
Reading: Chapter 2.

Week 3:

Polygon triangulation.
Reading: Chapter 3.

Week 4:

Linear programming.
Reading: Chapter 4.

Week 5:

Range searching.
Reading: Chapter 5.

Week 6:

Point location.
Reading: Chapter 6.

Week 7:

Voronoi diagrams.
Reading: Chapter 7.

Week 8:

Arrangements and Duality.
Reading: Chapter 8.

Week 9:

Delaunay triangulations. 3-D convex hulls.
Reading: Chapters 9 and 11.

Week 10:
- Geometric data structures.
- Reading: Chapter 10.

Copyright © 2023 Michael T. Goodrich, as to all lectures and videos; all rights reserved. All other course content, including Powerpoint and PDF slides, assignments, and course notes, is offered according to the license for this course.