Computational Geometry

CS 498 TC, Spring 2022


Just van Rossum, via DrawBot
Instructor
Jeff Erickson (jeffe@illinois.edu)
Lectures
Wed Fri 11:00–12:15
1131 Siebel Center and Zoom
Office Hours
Tue 10–11 and Fri 4–5
Via gather.town
Links


Announcements

May 17
Solutions to the final exam are available.
May 8
The final exam will be available on Gradescope Monday, May 9, at 4:30pm. Submissions are due Wednesday, May 11, at 4:30pm, 48 hours after the exam is released. After you open the exam, Gradescope will give you three hours to write and upload your solutions. Just like the midterm, you are welcome to use any official course materials linked directly from this web site, or anything you write yourself before you start the exam, but no other resources, either human, paper, or electronic.

Pleaes let me know ASAP if this scheduling creates a conflict with your other exams.

I will be holding extra office hours on Zoom on Monday, May 9, from 10:30–12:00 and 2:30–4:00. We are meeting on Zoom instead of gather.town so that I can record them; I will release video from office hours in the same private channel as the paper presentations as soon as possible.

May 6
Videos of the student paper presentations are available to registered students on an access-restricted MediaSpace channel.
May 4
Homework 4 solutions are available.
Apr 18
Homework 3 solutions are available.
Homework 4 is due Friday, April 28. This is the last homework.
Apr 4
If you are taking the class for four units, please register your paper presentation via the "assignment" on Gradescope by Friday, April 15. The assignment asks which paper you plan to present, which topics from that paper you plan to present, and (just to make sure you think about it) why. The assignment form also provides links to several computational geometry publication venues. The form will remain open through the end of the semester, so you can revise your plans at any time, but it's important to get started early; reading papers and preparing a good talk takes time! I am happy to discuss potential papers after class or in office hours.
Mar 29
Homework 3 is due Tuesday, April 11.
Mar 9
Graded midterms are available on Gradescope. Updated midterm solutions are also available.

There will be no lecture this Friday, March 11. Instead, I will hold office hours from 11 to 12:30 (on Gather), in addition to my usual Friday 4-5 office hours. Enjoy your spring break!

Mar 2
Solutions to the midterm are available. Each midterm problem has correct solutions that are not described in the handout; I may add more of these to the handout as I'm grading the exam.
Feb 26
Homework 2 solutions are available.

The midterm will be available on Gradescope tomorrow morning, and will be due Tuesday, March 1, at 8pm. After you open the exam, Gradescope will give you 2½ hours to write and upload your solutions. You are welcome to use any official course materials linked directly from this web site, or anything you write yourself before you start the exam, but no other resources, either human, papaer, or electronic. The exam covers the same material as the first two homeworks, or lectures through February 16.

Feb 15
Homework 1 solutions are available.
Homework 2 is due next Thursday, February 24.
Feb 1
Due to heavy winter weather, all classes are being held remotely for the rest of this week. Lectures on Wednesday, February 2 and Friday February 4 will be streamed over Zoom at the usual time.
Jan 30
Homework 1 is due next Thursday, February 10. (Sorry for releasing this so late.)
Jan 10
Welcome, everyone! Please pardon the dust while I get everything set up.


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