- 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.
- Once you open the Gradescope assignment, you have at most three hours to upload your solutions. 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 and anything you write yourself before starting the exam, but no other resources (paper, electronic, or human).
- You will submit your midterm solutions as a single PDF file. If you decide to handwrite your solutions, please use a black pen on plain white paper, and please use a scanning app to white-balance your PDF before submission.
- 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
- If you are taking the class for four units, please register your paper presentation using the form on Gradescope by 5pm on Friday, April 16. The form 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 form will remain open through the end of the semester, so you can revise your plans at any time, but
Thanks to side-effects on my second COVID vaccine, I am cancelling both my office hours this afternoon and tomorrow's lecture. I expect to resume regularly scheduled office hours on Friday. Next Tuesday, April 13, is the university's third instructional break daym, so our next lecture will be on Thursday, April 15.
Because of the unexpected gap in office hours and instruction, I am also extending the deadline for Homework 4 to Wednesday, April 14 (with the usual 24-hour grace period).
- 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.
- The drop deadline is now Wednesday, May 5 (the last day of instruction).
- Students can choose in the fourth week of May to have grades recorded as "Pass COVID" (for D– or higher) or "No Pass COVID" (for F). This replaces the usual CR/NC option.
- Feb 15
- Homework 2 is due Monday, March 1 at 8pm.
- Wednesday, February 17, is the first of our three sporadic days of "spring break". To make sure that everyone actually gets a break this week, there will be no lecture tomorrow (February 16); instead, I will use the usual lecture time as additional office hours.
- Because this is a new course for me (in more ways than one!), I would very much appreciate your feedback on how the course is going. I've created an this anonymous survey that you can fill out at any time, and as many times as you like, during the semester.
- 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!
Please enroll yourself on
Gradescope (for homework submission)
and Campuswire (for online discussions)
using the enrollment codes at the top of this page.
If you are not using your university email address to enroll on Gradescope,
please fill out this registration form.
If you require accommodations of any kind, please work with
DRES to provide Jeff with an
as soon as possible. In particular, exam accommodations require an accomodation
letter at least one week in advance. Please ask Jeff for further details.
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.