NOTE: This is a live document and is subject to change throughout the semester.
Spatial data is everywhere. How do we organize that data so that it can be efficiently processed? Moreover, how can we extract meaning out of this data? Computational Geometry provides tools for solving these questions. In this class, we will study convex hulls, Delauney triangulations, Voronoi diagrams, graph drawing, meshing, spatial decompositions, and many other geometric techniques. In addition, we will have opportunities to apply the techniques to real world problems.
The techniques of computational geometry are very useful! Indeed, they are part of the algorithmic foundations of Graphics, Visualization, Data Mining, Databases, Sensor Networks, Machine Learning, and Geographic Information Systems. They are also integral to simulation techniques used by Engineering, Computational Physics and Biology... just to name a few.
Tue, Thurs 12:15 - 13:30 412 Roberts Hall
David L. Millman, Ph.D.
Email: david.millman@montana.edu
Office hours: Mon 12:30 - 13:20, Thurs 15:00-15:50, or by appointment
Office: Barnard Hall 359
Github: dlm
Bitbucket: david_millman
Required:
- Computational Geometry: Algorithms and Applications by Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (CGAA in reading below).
Optional but recommended:
- David Mount's lecture notes (DMLN in reading below)
- Discrete and Computational Geometry by Satyan L. Devadoss and Joseph O'Rourke
- Computational Geometry in C (Second Edition) by Joseph O'Rourke
The lecture schedule is subject to change throughout the semester, but here is the current plan. Assignments and due dates will be updated as they're assigned in class.
| Date | Description | Assigned | Due | Recommended Reading |
|---|---|---|---|---|
| 1/10 | Intro | DMLN L1, CGAA 1 | ||
| 1/15 | Convex Hull | DMLN L3, CGAA 1.1 | ||
| 1/17 | Convex Hull | Homework 1 | DMLN L4 | |
| 1/22 | Line Segment Intersection | DMLN L5, CGAA 2.1 | ||
| 1/24 | DCEL & Subdivision Overlay | Homework 1 | DMLN L24, CGAA 2.2-.3 | |
| 1/29 | Polygon Triangulation | Homework 2 | DMLN L6, CGAA 3.2 | |
| 1/31 | Monotone subdivision and Art Galleries | CGAA 3.1-.2 |
| Date | Description | Assigned | Due | Recommended Reading |
|---|---|---|---|---|
| 2/05 | Trapezoidal Maps | Homework 2 | DMLN L9, GCAA 6.1-.2 | |
| 2/07 | Trap Map & Point Location | DMLN L10, CGAA 6.1-.2 | ||
| 2/12 | Exam 1 | Homework 3 | ||
| 2/14 | Exam Review & Half plane intersection | DMLN L7, CGAA 4.2 | ||
| 2/19 | Intersection and Duality | Homework 3 | DMLN L7, CGAA 8.2 | |
| 2/21 | Linear Programming | DMLN L8, CGAA 4.3-.6 | ||
| 2/26 | Voronoi diagrams | Homework 4 | DMLN L11, CGAA 7.1-.2 | |
| 2/28 | Fortune's algorithm | DMLN L11, CGAA 7.1-.2 |
| Date | Description | Assigned | Due | Recommended Reading |
|---|---|---|---|---|
| 3/05 | Delaunay triangulation properties | Homework 4 | DMLN L12, CGAA 9.1-.2 | |
| 3/07 | Delaunay triangulation RIC | DMLN L13, CGAA 9.3-.4 | ||
| 3/12 | Exam 2 | |||
| 3/14 | Exam Review & Discrete Voronoi Diagram | Homework 5 | ||
| 3/19 | NO CLASS (SPRING BREAK) | |||
| 3/21 | NO CLASS (SPRING BREAK) | |||
| 3/26 | Hulls, Envelopes, Del, & Voronoi | DMLN L16, CGAA 11.5 | ||
| 3/28 | Motion Planning | Homework 5 | DMLN L18, CGAA 13 |
| Date | Description | Assigned | Due | Proj | Recommended Reading |
|---|---|---|---|---|---|
| 4/02 | Arrangements | Homework 6 | X | DMLN L14, CGAA 8.3 | |
| 4/04 | Applications of Arrangements | DMLN L15, CGAA 8.4 | |||
| 4/09 | Orthogonal Range searching & KD tree | Homework 6 | X | DMLN L32, CGAA 5.1, 5.2 | |
| 4/11 | Orthogonal Range trees | DMLN L33, CGAA 5.3, 5.6 | |||
| 4/16 | Well separated pair decomposition (WSPD) | Homework 7 | X | DMLN L19 | |
| 4/18 | Applications of WSPD | DMLN L20 | |||
| 4/23 | Geometric sampling & VC-dimension | Homework 7 | X | DMLN L21 | |
| 4/25 | Eps-Nets & Cutting Lemma | DMLN L21 & Eps-Nets and CG - J Matousek |
| Date | Description | Assigned | Due | Proj | Recommended Reading |
|---|---|---|---|---|---|
| 5/02 | (Finals week) 12:00-13:50 | X |
- Cake Cutting
- Approximate Nearest Neighbors
- Curve & Surface Reconstruction
Your grade for this class will be determined by:
- 30% Group Project
- 40% Homework (lowest homework is dropped)
- 15% Exam 1
- 15% Exam 2
Attendance in class with not be taken but students are responsible for all material covered in class. Attendance is strongly recommended.
There will be regular homework assignments (about every other week) consisting of written problems (and possibly a few coding exercises). Homeworks will be posted in the schedule. Solutions should be submitted as a PDF on Brightspace. (The tool that I use for grading papers only works with PDFs, so any file format other than PDF will receive a 0.) Homework is due at 23:59 on the due date. Late homework will not be accepted.
You do NOT need to write up your solutions with LaTex, but I highly encourage you to do so. You can find some resources for getting started with latex (and for making figures, and keeping all those files safe with git) in the student resources repo.
I encourage collaboration, see collaboration section for details.
Group discussions, questions, and announcements will take place using Slack. It is okay to send me a direct message or email if you have a question that you feel is not appropriate to share with the class. If, however, you send me an message with a question for which the response would be useful to the rest of the class, I will likely ask you to post publicly.
We will use the Computational Topology and Geometry (CompTaG) slack group. Please join the group and join the #csci-591-sp19 channel. There are lots of other discussions and announcements going on in the group for various CompTaG projects. Feel free to hop on #general and say "Hi!" to the group. Feel free to poke into various public groups, listen quietly or get involved in the conversation.
Collaboration IS encouraged, however, all submitted individual work must be your own and you must acknowledge your collaborators at the beginning of the submission.
On any group project, every team member is expected to make a substantial contribution. The distribution of the work, however, is up to the team.
A few specifics for the assignments. You may:
- Work with anyone in the course.
- Share ideas with others in the course
- Help other teams debug their code or proofs.
You may NOT:
- Submit a proof or code that you did not write.
- Modify another's proof or code and claim it as your own.
Using resources in addition to the course materials is encouraged. But, be sure to properly cite additional resources. Remember, it is NEVER acceptable to pass others work off as your own.
Paraphrasing or quoting another's work without citing the source is a form of academic misconduct. Even inadvertent or unintentional misuse or appropriation of another's work (such as relying heavily on source material that is not acknowledged) is considered plagiarism. If you have any questions about using and citing sources, you are expected to ask for clarification. My rule of thumb is if I am in doubt, I cite.
By participating in this class, you agree to abide by the student code of conduct. Please review the policy.
Except for note taking and coding, please keep electronic devices off during class, they can be distractions to other students. Disruptions to the class will result in you being asked to leave the lecture and will negatively impact your grade.
If you have a documented disability for which you are or may be requesting an accommodation(s), you are encouraged to contact me and Disabled Student Services as soon as possible.
Want to learn even more about computational geometry?! While not in any way required as part of the class, please, feel free to participate in any of the fun happenings of the CompTaG research group! We are a very active group and there are lots of opportunities for you to get involved if you would like. All events take place at Faculty Court 23 (CompTaG research house).
-
Every Tue 14:00-17:30 CompTaG hosts a Prove-a-thon. We use the time to work on research problems in Computational Geometry (and Topology). Feel free to come by and find out what we are working on.
-
Every Wed 15:00-15:50 CompTaG hosts a research seminar. We cover interesting research papers. Usually, we cover about 1 paper every 2-3 weeks, but focus on understanding content over covering a lot of material. Feel free to join up or enrolls in CSCI X94 for credit.
-
Every Fri 14:00-17:30 CompTaG hosts a Hack-a-thon. We use the time to work on code related projects. Feel free to come by and start working with CGAL or try implementing some of the algorithms that we are learning in class.
You can also check out research papers. Some of the best conferences are:
- Symposium on Computational Geometry (SoCG)
- Symposium on Discrete Algorithms (SoDA)
- Symposium on Theory of Computing (STOC)
- Foundations of Computer Science (FoCS)
- European Symposium on Algorithms (ESA)
But, let me know if you have a specific interest and I can point you in a direction to help you get started.