Computational Geometry
Announcements
- May 21
-
- Solutions to the final exam" are available.
- The final exam has been graded; scores and feedback are available on Gradescope.
- Apr 23
-
- Apr 23
-
A tentative schedule of paper presentations is available. Presentations are scheduled for next Thursday, April 30, and Tuesday, May 5, but if necessary we will schedule an extra meeting on Thursday, May 7.
- Apr 22
-
- Apr 7
- If you are taking the class for four units, please register your paper presentation via the "assignment" on Gradescope by Friday, April 17. 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 also provides links to several computational geometry publication venues. The "assignment" 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, either after class or in office hours.
- Mar 29
- Homework 3 is due Tuesday, April 14.
- Mar 18
-
- Mar 2
- A student pointed out that I announced in class last week that the midterm would be due Wednesday, March 4, not Tuesday, March 3 as previously announced here. The exam is due Wednesday. I apologize for the mixup; I have correccted both the exam and the submission deadline on Gradescope.
- Mar 1
-
- The midterm is available on Gradescope. Please read the instructions on the cover page before opening the exam. Solutions are due Wednesday, March 4, at 8pm, and must be uploaded at most 2½ hours after you open the exam.
- There is also zero-credit 15-minute practice exercise on Gradescope to make sure you know how scan and upload documents to Gradescope quickly.
- Feb 16
- Homework 1 solutions are available.
- Feb 15
- There are no office hours this Wednesday, February 18, and no lecture this Thursday, February 19; I will be out of town. Depending on how far we get in class on Tuesday, I may post an extra lecture video for Thursday.
- Feb 12
- Homework 2 is due Thursday, February 26.
- Feb 5
- A LaTeX homework template is available both directly and on Overleaf.
- Jan 29
- Homework 1 is due Wednesday, February 11. Please read the homework policies on the last page of the homework handout.
- Jan 13
- Welcome, everyone! Please pardon the dust while I get everything set up.
-
If you require accommodations of any kind, please 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.
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.
