Just van Rossum, via DrawBot

Computational Geometry

CS 498 TC, Spring 2021

Instructor
Jeff Erickson (jeffe@illinois.edu)
Lectures
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)
Links


Announcements

Jun 19
All homework and exam solutions have been removed from the web site.

Thanks everyone for a great semester! (Well, you know, except for that whole pandemic thing.)

May 19
The final exam has been graded, and course grades have been reported to the registrar. The average score on the final exam was significantly lower than for the midterm; to compensate for this discrepancy, I swapped the weights of the midterm and the final exam in the overall grade calculation (unless that lowered your grade).

Regrade requests can be submitted until Friday, June 11.

May 11
Solutions to the final exam are available.
May 7
The final exam will be released on Gradescope this Sunday, May 9 at 8am, and will be due Monday, May 10 at 10pm.

The exam will cover all material in the class through April 15—including line arrangements, but not the funnel algorithm, Minkowski sums, or visibility graphs—or equivalently, the material actually covered in the homeworks (except HW5.4). The final exam will have a bit more emphasis on material presented after the midterm.

You may find the exams and practice material from David Mount's recent computational geometry class helpful. You can also find good study problems in the appropriate chapters of “Four Marks”.

The format and length of the final exam will be exactly the same as the midterm.

May 2
Apr 22
Everyone please fill out an evaluation form for this class on ICES Online from tomorrow through Thursday, May 6. Your feedback is extremely important, especially narrative feedback. (Please submit evaluations for all your other courses as well!)
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