This is a course on Computational Geometry, a topic in algorithm design and analysis.
The course will cover standard computational geometry topics such as computation of convex hulls and
Voronoi diagrams, basic geometric algorithm techniques such as sweep line algorithms and use of
duality, basic geometric data structures such as trapezoidal decompositions and binary space
partitions, and geometric optimization algorithms.
Some emphasis will be placed on the real world use of geometric algorithms.
Specific topics will be determined as the semester progresses.
The official course syllabus can be found here.
All policies from both the syllabus and website apply, but if there is a contradiction, then the
syllabus takes preference (but do email Kyle so he can fix the issue!).
Announcements and updates to the schedule including recommended reading will take place on the
main course webpage.
We'll also make announcements on eLearning.
Additional details on the course and its policies are given below.
Do make yourself familiar with them to avoid confusion later.
And be sure to carefully read the writing policies and advice so we may
fairly grade you for the work you do on the homework.
Welcome! We hope you find this course both interesting and useful.
Most of the lectures will be based on the excellent lecture notes of David Mount available here.
The standard textbook for Computational Geometry courses is
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars:
Computational Geometry—Algorithms and Applications—Third Edition.
Springer 2008, often referred to as the "Dutch book" or the "three Marks" book.
We will also pull examples and proofs out of the textbook, but we will not follow it too closely.
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.
We will always write out homework problems instead of just pointing you to
the textbook.
Your grade will be determined by a combination of homework, a project proposal, and a final project
report.
Your grade will be determined by a weighted sum of these items as shown below.
- Homework: 50%
- Project Proposal: 10%
- Final Project Report: 40%
Grade cutoffs will be determined by looking at the distribution of scores in the class.
However, there is no fixed curve.
If everybody performs well, then everybody can get top grades.
Students are highly encouraged to talk to Kyle to get a better idea of
where they stand before considering dropping the course.
We will release four or five homework assignments throughout the semester.
They will "generally" be released bi-weekly and be due on eLearning immediately before class on the
day they are due.
Starting March 15th, submissions may be turned in late at Kyle's discretion.
In the case of an unusual circumstance such as a documented extreme illness or
injury, contact Kyle as soon as possible to arrange accommodations.
Collaboration and submission
Homework assignments can be done individually or in groups of up to three students and turned in via
eLearning.
Since eLearning is not well-equipped to handle group submissions, a single member of each group
should turn in their assignment, and we'll make sure everybody in the group gets the same score for
the submission.
Clearly write your name, the homework number, and
the problem number at the top of every page.
For example, you might write "Kyle Fox and Teaching Assistant, HW0 #2".
In addition, start each numbered homework problem on a new page
so we don't miss any problems.
We hope you will put in an honest effort to solve each homework problem without having to rely on
resources outside of the course material.
However, we also want to give you the opportunity to discuss class material with students outside
your group and access other kinds of outside help as needed.
If you use a solution from an outside source, such as a web page, a journal paper, a different
algorithms textbook, or your mom, or if choose to work with students from the class outside your
group, then
you must rewrite the solution in your own words, and you must properly cite your
source.
Do not forgot to rewrite in your own words; the goal here is not to teach us what you found outside
the course material, but to convince us that you actually understand it yourself.
You may assume we have knowledge of the official course material or prerequisites without citation,
but nothing else.
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, and we will report suspected violations to
the Office of Community Standards and Conduct.
A correct solution based on a cited source and written in your words is still worth full credit.
When in doubt, cite your source!
(That said, now would be a good time to mention that many of these course policies and the writing
advice given here are taken from algorithms course websites by
Jeff Erickson and
Erin Wolf Chambers.)
There may be websites out there that offer solutions to some of the problems we will post.
Be very careful with these sites.
The solutions are sometimes incorrect, and in cases where they are correct, they don't offer a full
or understandable justification for what they are doing.
If you find yourself frequently relying on outside sources, then you may not be
putting enough effort into learning computational geometry yourself, and your ability to use it
outside the class will suffer.
Regrades
Requests for regrades should be done within one week of an assignment or exam being returned.
Please be considerate of whether your request is legitimate.
All regrade requests must include an explanation of why you feel you were graded incorrectly.
Regrade means regrade, so your score may actually decrease.
Extra credit
We may occasionally offer opportunities to gain extra credit by solving additional challenging
problems or doing other relevant work.
However, these opportunities (if any) will be rare, and you should not depend upon them to get the
grade you desire.
The final grade cutoffs will be determined before taking extra credit into account, so these
opportunities will only help and never hinder students.
The citation policy does not apply here.
You must do extra credit work on your own.
Please see this page for information on the class projects.
Attendance
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.