This is a special topics course in computational geometry, an algorithms topic that is important to
many application domains, including computer graphics, VR, geographic information systems, robotics,
databases and data analysis, etc.
Specific topics will include basic computational geometry topics like computing convex hulls,
computing Voronoi diagrams and Delaunay triangulations, motion planning, and the main methods for
developing geometric algorithms. We will also discuss various geometric data structures for point
location, range searching, and so on, some geometric approximation algorithms, and possibly some
topics from computational topology if time permits.
The course emphasizes a theoretical approach, but I hope the topics are useful and interesting to
the more practically motivated as well.
The official course syllabus can be found here.
Please look over it carefully.
The course website is intended as a supplement to the syllabus, but whatever is written in the
syllabus is the final word on a subject.
Announcements and updates to the schdule including recommended reading will take place on the
main course webpage.
Additional details on the course and its policies are given below.
Please make yourself familiar with them to avoid confusion later.
There is even some advice on how to perform better on homework.
Welcome! I hope you find this course both interesting and useful to your future career.
Reading
The required textbook is Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars:
Computational Geometry—Algorithms and Applications—Third Edition, also
known as the 3 Marks book.
I also highly recommend the online lecture notes by David M. Mount available
here.
While I will pull many examples from both, you should consider the textbook and lecture notes as
supplements to the lectures and not your only source for some material.
That said, the more you read outside of lecture, the more examples and details you will see, and
hopefully your reading will lead to a deeper understanding of the class material.
I will write out homework problems instead of just pointing you to the textbook.
Grading
Your grade will be determined by three things: homework, a midterm project proposal, and a final
project report and presentation.
Your grade will be determined by a weighted sum of these three items as shown below.
- Homework: 60%
- Project Proposal: 10%
- Final Report and Presentation: 30%
There is no fixed scoring rubric as your final grade will be determined by how the rest of the class
performs and how difficult the assignments are.
This is a special topics course, so most students should get a good grade as long as they put in an
honest effort.
Homework
I intend to release homework once every few weeks.
No late homework will be accepted.
You may work in small groups of up to three students on the homework.
Please see the section on collaboration below.
Collaboration
Homework assignments may be done in small groups of up to three students.
Each group of students working together should turn in a single set of solutions.
Otherwise, you are expected not to use outside sources while solving homework problems.
However, if you must use outside sources (or write solutions in close collaboration with other
students outside your group) to find good solutions then you may cite that source and still receive
full credit for the solution.
Material from the lecture, the required textbook, or prerequisite courses need not be cited.
Failure to cite other sources or failure to provide solutions in your own words, even if quoting a
source, is considered an act of academic dishonesty.
Regrades
Requests for regrades should be done within one week of an assignment being returned.
Please be considerate of whether your request is legitimate, and please be prepared to explain why
you feel you were graded incorrectly.
Regrade means regrade, so your score may actually decrease.
General advice
Please make sure your answers are readable, and please staple together your solutions if they appear
on multiple sheets of paper.
Any homework solution that is unintelligible will receive a score of 0 regardless of correctness.
It is not required, but I highly recommend you typeset your homework solutions, preferably using
LaTeX.
Proficiency in LaTeX is a good skill to have if you ever plan to write math in the future.
This class emphasizes a theoretical approach, and I will often ask you to design algorithms or
explain things on the homework.
To receive full credit, you must prove your solutions are correct.
I expect you to use about the same level of rigor that I use during lectures.
Remember, if you are unable to explain why your algorithm is correct with a short proof, then not
only will you lose points, but your algorithm is probably not correct in the first place!
I can only grade what I am given, even if you appear to have the right answer in mind.
Please do not attempt to describe algorithms by only giving examples and assume I can fill in the
details.
As a general tip, a student comfortable in algorithms (not necessarily geometry) should be able to
read your homework solution, understand whatever algorithm you have in mind, and feel confident
about its correctness, even if they have never seen the specific homework problem before.
Class Projects
Please see this page for information on the class projects.
Attendance Policy
It is the Computer Science Department’s policy that absence in three consecutive lectures will result in the course grade being lowered by one letter and absence in four consecutive lectures will automatically result in a failing grade (F) in the course.