Computational Geometry

CS 498 TC, Spring 2022

Main  ❖  Syllabus  ❖  Schedule  ❖  Resources

Caveat

Some aspects of this syllabus may change as the semester progresses; I will announce any significant changes well in advance of their effect.

Prerequisites

CS 374 or an equivalent undergraduate algorithms course. Specifically, this course assumes a solid background in the following:

• Basic algorithm design techniques (divide-and-conquer, dynamic programming, graph modeling, ...)
• Basic algorithm analysis techniques (asymptotic notation, evaluating sums and recurrences, ...)
• Basic graph problems/algorithms (traversal, topological sort, shortest paths, ...)
• Basic data types/structures (balanced binary trees, priority queues, hashing, adjacency lists, ...)

Familiarity with discrete probability and basic linear algebra is also helpful.

Recommended Reading

Most of my lectures will follow these sources fairly closely.

• [Marks] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational Geometry: Algorithms and Applications, 3rd edition, Springer, 2008. Commonly known as “Four Marks” or “The Dutch Book”. PDF version available through the university's library proxy server.
• [Mount] David Mount, CMSC 754: Computational Geometry, 2021. Lecture notes from his Fall 2021 computational geometry course at Maryland. (Local cache, local cache of Dave's scribbles)
• [Swiss] Luis Barba, Bernd Gärtner, Michael Hoffmann, and Emo Welzl, Geometry: Combinatorics and Algorithms, 2019. Lecture notes from their computational geometry course at ETH Zürich. (Local cache)

I will provide additional typeset lecture notes and/or paper links as necessary. You can find additional useful references on the resources page.

Credit

Like most 400-level computer science classes at Illinois, this class can be taken either for 3 credits or 4 credits. (For administrative purposes, there are two separate 3-credit sections, one for undergraduates and one for graduate students, but they are identical.)

By default, the 4-credit section is available only to graduate students. However, undergraduates can earn honors credit by doing the additional work required for the 4-credit section. Please ask me for details.

Grading

Course grades are based on 4–6 biweekly(ish) homework assignments, a midterm exam, a take-home final exam, and (for 4-credit students only) a paper presentation.

• 3-credit students: 40% homework + 25% midterm + 35% final exam
• 4-credit students: 35% homework + 20% midterm + 30% final exam + 15% presentation

Homework averages will be based on the highest $c\cdot k$ homework scores, where $c$ is the number of credits (3 or 4) and $k$ is the number of homework assignments.

Class-Specific Policies

We will follow essentually the same course policies as CS 473. In particular:

• Teams of up to three students can submit joint homework solutions. All team members should be listed on the first page of each homework submission.
• I strongly encourse students to collaborate on homework (and practice for exams) in larger study groups. However, each submitted solution must be written independently and must cite all contributions from larger groups amd/or their members. Collaboration on exams is not allowed.
• The midterm and the final are open-book, closed-everything-else exams. You are welcome to use any of this semester’s official course materials and anything you write yourself before starting the exam, but no other resources (paper, electronic, or human).
• Whenever a homework or exam problem asks you to design an algorithm, your solution should include a clear description of the algorithm (usually in pseudocode), an analysis of the running time, and justification of correctness (if correctness is not obvious). Faster algorithms are worth more points, but only if they are correct.
• Homework and exam grades will depend not only on correctness and speed, but also on clarity and style. Your solutions should be complete and mathematically precise, but at the same time, easy to understand and concise. Don't submit your first draft!
• Academic integrity: Generously cite your sources. Use your own words. Don't put your name on work that isn't yours.
• Homework will be submitted on Gradescope as separate PDF files for each problem. Exactly one team member should upload each solution and identify all other team members.
• Homework can be submitted up to 24 hours after the official deadline for a 10% score penalty. No homework will be accepted more than 24 hours after the deadline. (Remember that your lowest several homework scores will be dropped.) The 24-hour grace period does not apply to exams.
• Under extreme circumstances, such as a documented disability, illness, injury, or other emergency, I may forgive homework or even the midterm. Please let me know as soon as possible, preferrably before the relevant deadline.
• Students who require accommodation for a disability should work with DRES to provide an accommodation letter as soon as possible. In particular, exam accommodations require an accomodation letter at least one week in advance. Please ask me for further details.
• There is no requirement to attend lectures in person. All class resources including lecture videos, homeworks, and exams will be available online. Do not come to class in person if you feel ill, if you feel unsafe, if you have recently tested positive for COVID, or if you have had an exposure to COVID that requires testing and/or quarantine.

Class-Agnostic Policies and Resources

• All members of the Illinois Computer Science department—faculty, staff, and students—are expected to adhere to the CS Values and Code of Conduct. The CS CARES Committee is available to serve as a resource to help people who are concerned about or experience a potential violation of the Code. If you experience such issues, please contact the CS CARES Committee. (I am a member of the CARES committee; feel free to contact me directly.)
• The CS Mental Health committee has collected a comprehensive list of mental health resources.
• Everyone who attends class in person must have building access (which requires being vaccinated) and must properly wear a face covering at all times. See the university's Spring 2022 COVID guidelines.
• Important information about university policies regarding academic integrity, anti-racism and inclusivity, disability accommodations, FERPA rights, mental health resources, religious observances, and sexual misconduct reporting are listed on a separate page.

Advice

• Kindness > Honesty > Clarity > Correctness > Efficiency. First make it clear; then make it work; then make it fast; then make it faster. (Notice that “perfection” and “cleverness” don't even make the list.)
• Homework will be due roughly every other week, but I strongly recommend starting on each homework assignment as soon as it is released. Don't wait until two days before the deadline to start!
• I strongly recommend typesetting your homework solutions in LaTeX, especially if you have poor handwriting. (I'll post a LaTeX homework template here soon.) In particular, I recommend collaborating on LaTeX solutions via Overleaf. If you must handwrite your solutions, please write using dark ink (not pencil) on plain white unlined paper, and please use a scanning app (to align margins, increase contrast, and the like) instead of uploading raw photos.
• For this course especially, illustrations can be extremely helpful in communicating intuition and examples, but don't confuse intuition and examples for mathematical precision. I strongly recommend using a vector-graphics program like Ipe, Inkscape, LibreOffice Draw, or OmniGraffle. Every picture is worth 1000 words, so you should take as much time and care creating each picture as you would writing 1000 words.