Just van Rossum, via DrawBot

Computational Geometry

CS 498 TC, Spring 2021

Jeff Erickson (jeffe@illinois.edu)
TuTh 11:00–12:15 via Zoom
Office Hours
Via gather.town
  • Class: Wed 3–4 and Fri 9–10 (tentative)
  • Public: Fri 3–4 (tentative)


Apr 16
Homework 4 solutions are available.
Apr 14
Homework 4 is due Wednesday, April 28 at 8pm. Only four problems again. This is the last homework!
Apr 7
Apr 2
Mar 29
Homework 4 is due Monday, April 12 at 8pm. Only four problems this time.
Mar 20
Wednesday, March 24, is the second of our three sporadic days of "spring break". To make sure that everyone actually gets a break this week, there will be no lecture Tuesday (March 23); instead, I will use the usual lecture time as additional office hours.
Mar 18
Homework 3 has been revised. (Problem 4 is easier than I originally thought, and problem 5 was just broken.)
Mar 15
Homework 3 is due Monday, March 29 at 8pm. (All future homework deadlines are now one week later.)
Mar 9
Solutions to Midterm 1 are available.
Mar 5
Midterm 1 will be released on Gradescope Sunday, March 7 at 8am, and will be due Monday, March 8 at 10pm. Once you open the Gradescope assignment, you have at most three hours to upload your solutions. (In particular, if you start Monday after 7pm, you will have less than three hours.) The exam is designed to be taken in 90 minutes.

This is an open-book but closed-everything-else exam. You are welcome to use any of this semester’s official course materials—including the recommended textbook, lecture notes, lecture scribbles, lecture videos, and homework solutions—and anything you write yourself before starting the exam. All other materials—including course materials from past semesters, materials from courses elsewhere, other internet resources, other textbooks, and (most importantly) other people—are not permitted. Do not communicate with anyone about the exam before Monday at 10pm.

You will submit your midterm solutions as a single PDF file. I recommend writing and drawing your solutions by hand and then scanning to create your PDF, but you are welcome to use LaTeX/Google Docs/Word/whatever if you can do that quickly enough. As with homework, you can submit as many times as you like; only the most recent submission before the deadline will be graded.

There is a "Practice Midterm 1" on Gradescope with the same format as the actual midterm, but with a 60-minute time limit. (The questions on the practice exam are just Homework 2.) I strongly recommend scanning and uploading a hand-written test document to see how long the entire process takes.

The exam will cover the same material as Homeworks 1 and 2: convex hulls, duality, segment intersection, plane sweep, point-in-polygon testing, winding numbers, planar straight-line graphs, and Euler's formula. This roughly corresponds to Chapters 1–3 of “Four Marks” (plus a bit of material on duality from Chapter 8); the problems at the end of those chapters are good review material.

Mar 3
Homework 2 solutions are available.
Feb 19
Source files for the Homework 1 solutions are available. You are welcome to use these as a template for future LaTeX submissions. If you want to modify the figures, you need OmniGraffle and Source Sans Pro font (or its younger cousin).
Feb 18
Homework 1 solutions are available.
Feb 16
Please see the recent Massmail and official policy documents about modified drop deadlines and pass/no-pass grading options for this semester.
Feb 15

Feb 1
Homework 1 is due Monday, February 15 at 8pm.

I expect to include five problems in each homework assignment. Homework averages will be based on the highest $c\cdot k$ homework scores, where $c$ is your number of credits and $k$ is the number of homework assignments. So on average, 3-credit students should submit solutions for at least three problems in each assignment, and 4-credit students should submit at least four problems in each assignment.

Jan 26
There is an unofficial class Discord! Please feel free to join, and please let me know if you think Discord works better than Campuswire.

Jan 6
Welcome, everyone!

About this class

This class is an introduction to the design, analysis, and applications of algorithms for fundamental problems where the input are naturally interepreted as geometric objects. Specific problems we may consider include convex hulls, Voronoi diagrams, line segment intersection, polygon triangulation, geometric range searching, low-dimensional linear programming, geometric shortest paths, and visibility. Computational geometry has immediate applications in many other research areas, including computer graphics, mesh generation, geographic information systems, VLSI design, and robotics. While we may briefly consider these applications, the class will primarily focus on theoretical results and techniques.

In short, this is an algorithms class, with lots of pretty pictures! Lectures, homeworks, and exams will assume a solid background in algorithms, at least at the level of CS 374.

For more information, please see the course syllabus.


Creative Commons License   Powered by MathJax