April 2: Homework 4 has been released. The LaTeX source for the assignment is available as well in case you find it helpful for writing solutions. Your submission to eLearning is due Friday, April 24th (three weeks from today) by the end of the day.
March 31: The video for Lecture 19 is now available on YouTube.
March 30: Sorry about the second announcement today, but we have added two links to the Course Homepage on eLearning. One is for a recurring WebEx meeting we'll use for live lectures. The link shouldn't change, so we won't bother you with reminders after today. If you're unable to attend the live lecture, we'll also post a local recording of the lecture to YouTube. The second link is for the normally scheduled group office hours. If you'd prefer a private office hours meeting, please send Kyle an email.
March 30: Kyle has to cancel office hours for Tuesday, March 31st. If you would like to schedule for another time, please send him an email.
March 27: A page linking to copies of your project proposals is now available on the eLearning Course Homepage. Please look it over to see if others have similar interests to your own, and consider grouping up for your projects. I also provided feedback on your individual proposal submissions in cases where I thought I had some useful suggestions to offer.
March 26: The video for Thursday's test lecture is now available on YouTube. We apologize for the low quality of the video. Future lecture videos should look better than this one.
March 24: In order to slow the spread of CORVID-19, the class is transitioning to a fully online format. Your final homework assignment and projects will remain as detailed in the last announcement. However, you need to be aware of the following changes to the course structure.
We hope these plans work well for you and welcome any feedback you have as we try to minimize disruptions to the normal class experience. Naturally, these plans are subject to change as we discover what technology and presentation formats do and do not work well.
And if you are interested, Kyle will be doing a full test lecture this Thursday, March 26th at 11:30am on WebEx, covering the material he was not able to cover on Thursday, March 5th. You not required nor expected to attend, but if a few students show up to ask questions or to give feedback on the experience, we would greatly appreciate it. The link to the WebEx meeting will be sent in an email some time before the lecture.
March 13: Due to the extended Spring break and by student request, we are making some changes to deadlines and anticipated work.
Please remember that working in groups for the final homework and project is optional. You are encouraged to seek remote solutions if you decide to do your work in groups, and please do not meet up if you are sick. Kyle will spend time during the extended Spring break to figure out how to make online lectures and office hours go as smoothly as possible.
March 11: An incomplete list of projects from a past semester has been added to the course projects page. You may want to look it over for inspiration for your own projects. Do not simply ask to repeat one of these projects.
March 9: Homework 3 solutions are now available.
March 5: Very sorry about the late notice, but Kyle needs to cancel class for today Thursday, March 5th. The lecture notes he would have used can be found here. This lecture covers interesting "bonus" material not strictly related to any algorithms or applications we'll discuss, so we may not cover it in person until later in the semester if at all. Please look over the notes and Chapter 16 of Mount anyway.
February 28: Proposals for the course project are due Friday, March 13th on eLearning. Please see the course projects page for more details. Unlike homework, each individual student should submit their own proposal.
February 27: Homework 2 solutions are now available.
February 26: The LaTeX source for Homework 3 is now available in case you find it helpful for writing solutions.
February 21: Homework 3 has been released. It is due Friday, March 6th by the end of the day.
February 20: After further consideration, Homework 2 Problem 1 does not appear to have a straightforward \(O(n)\) time solution. Please aim for \(O(n \log n)\).
Problems 1 and 3 have been updated with hopefully more helpful hints. To give you time to take advantage of them, the deadline has been extended to Monday, February 24th. Homework 3 will likely be released tomorrow Friday, February 21st.
February 19: Sorry about the cancelled office hours last Monday. To make up for them, Kyle is holding office hours tomorrow, Thursday February 20th from 10am to 11am in his office.
February 12: Some students have pointed out that Homework 2 Problem 1 has a relatively simple \(O(n)\) time solution. Homework 2 has been modified to ask for one. Anybody that turns in a fully correct \(O(n \log n)\) time solution instead will still get full credit.
February 11: Homework 1 solutions are now available.
February 7: Homework 2 has been released. It is due Friday, February 21st by the end of the day.
January 28: Very sorry about the late notice, but Kyle needs to cancel his office hours for today. To make up for it, he'll hold additional office hours this Thursday, January 30th from 1:30pm to 2:30pm. Again, please send Kyle an email if you need to schedule office hours outside the normal times.
January 24: Homework 1 has been released. It is due Friday, February 7th by the end of the day. If you would like to use LaTeX to write your solutions, you may want to start with this template.
Also, Kyle needs to move his office hours for next Monday, January 27th from the normal time to 3 to 4pm. Sorry about the inconvenience. Feel free to send Kyle an email if you need to schedule office hours outside the normal times.
January 14: The CS department requires everybody to fill out forms verifying they have taken the necessary prerequisites for their individual classes. Please fill out the prerequisite form using a digital signature (instructions) and submit it in the Prerequesite Form assignment on eLearning. If you're unable to do a digital signature for any reason, then please print the form, complete and sign it, scan it, and upload it to the assignment. Please do this by next Tuesday, January 21st. The prerequesite course is CS 5343.
January 13: Hi all, and welcome to CS 6301 — Special Topics in Computer Science — Computational Geometry! I sincerely hope you all enjoy and get a lot out of this semester.
We'll be using eLearning for homework submissions, grade reporting, and announcements. Everything else, including the lecture schedule, reading recommendations, notes, and course policies can be found on the course website.
Date | Subject/Event | Reading | Notes |
---|---|---|---|
Tue, Jan. 14th | Administrivia, convex hulls, modified Graham's scan | 3Marks Preface, 1; Mount 1, 3; lecture notes | |
Thur, Jan. 16th | Finish Graham's scan, lower bound on convex hulls, Jarvis's march (gift wrapping), output sensitivity | Mount 3, 4; lecture notes | |
Tue, Jan. 21st | Chan's algorithm ['96] for convex hulls, line segment intersection and plane sweep [Bentley, Ottmann '79] | 3Marks 2–2.1; Mount 4–5; lecture notes | Prerequesite form due (instructions) |
Thur, Jan. 23rd | Finish line segment intersection, doubly-connected edge lists, merging planar subdivisions | 3Marks 2.1–2.3; Mount 5, 23; lecture notes | |
Tue, Jan. 28th | Monotone polygon triangulation [Garey et al. '78], monotone polygon decomposition [Lee, Preparata '77] (for triangulation) | 3Marks 3; Mount 6; lecture notes | |
Thur, Jan. 30th | Finish monotone polygon decomposition, halfplane intersection, point-line duality | 3Marks 3.2, 4.2, 11.4; Mount 6–7; lecture notes | |
Tue, Feb. 4th | Duality of envelopes and convex hulls, linear programming, incremental construction | 3Marks 4.3, 11.4; Mount 8; lecture notes | |
Thur, Feb. 6th | Randomized incremental construction and backward analysis for linear programming, trapezoidal maps | 3Marks 4.4, 6–6.1; Mount 8, 9; lecture notes | Homework 1 due Friday, February 7th (solutions template) (actual solutions) |
Tue, Feb. 11th | Trapezoidal map construction and point location | 3Marks 6; Mount 9, 10; lecture notes | |
Thur, Feb. 13th | Finish point location, start Voronoi diagrams | 3Marks 6–7.2; Mount 10, 11; lecture notes | |
Tue, Feb. 18th | Voronoi diagrams, Fortune's algorithm ['87] | 3Marks 7–7.2; Mount 11; lecture notes | |
Thur, Feb. 20th | Delaunay triangulations, uses and properties | 3Marks 9–9.2; Mount 12; lecture notes | Homework 2 due Monday, February 24th (solutions) |
Tue, Feb. 25th | Delaunay triangulations, maximizing angles, construction | 3Marks 9; Mount 12, 13; lecture notes | |
Thur, Feb. 27th | Line arrangements, construction, zone theorem | 3Marks 8.3; Mount 14; lecture notes | |
Tue, Mar. 3rd | Line arrangement applications, sorting angular sequences, narrowest k-corridor, halfplane discrepancy, plane sweeps | 3Marks 8; Mount 15; lecture notes | |
Thur, Mar. 5th | Class cancelled | Homework 3 due Friday, March 6th (LaTeX source) (solutions) | |
Tue, Mar. 9th | Robot motion planning, configuration spaces, Minkowski sums | 3Marks 13; Mount 20; lecture notes | |
Thur, Mar. 12th | Robot motion planning continued, visibility graphs, shortest paths | 3Marks 15; Mount 29; (Mount 27 for topological plane sweep); lecture notes | |
Tue, Mar. 17th | No class due to Spring break | ||
Thur, Mar. 19th | No class due to Spring break | Project proposals due Friday, March 20th | |
Tue, Mar. 24th | No class due to Spring break | ||
Thur, Mar. 26th | No class due to Spring break; test lecture on Delaunay triangulations and 3D lower convex hulls, Voronoi diagrams and 3D upper envelopes | 3Marks 11.0, 11.5; Mount 16; lecture notes; lecture video (sorry about the low quality) | |
Tue, Mar. 31st | Orthogonal range searching, kd-trees | 3Marks 5–5.2; Mount 31; lecture notes; lecture video | |
Thur, Apr. 2nd | Orthogonal range trees, fractional cascading, interval trees, window queries for orthogonal segments(?) | 3Marks 5.3–5.6, 10–10.1; Mount 32, 33; lecture notes; lecture video | |
Tue, Apr. 7th | Curve similarity, Hausdorff distance, Fréchet distance | lecture notes | |
Thur, Apr. 9th | Approximation algorithms, k-center | Erickson J.2, J.10–J.11 | |
Tue, Apr. 14th | Well separated pair decompositions (WSPDs), construction of WSPDs | Mount 17 | |
Thur, Apr. 16th | Applications of WSPDs | Mount 18 | |
Tue, Apr. 21st | Geometric sampling, VC-dimension | Mount 19 | |
Thur, Apr. 23rd | Geometric sampling continued, learning a shape, geometric set cover and hitting set | Mount 19 | Homework 4 due Friday, April 24th (LaTeX source) |
Tue, Apr. 28th | Metrics, embeddings, Johnson-Lindenstrauss "lemma", Bourgain's theorem | An elementary proof of a theorem of Johnson and Lindenstrauss. Sanjoy Dasgupta and Anupam Gupta. Journal Random Structures & Algorithms, 22(1):60–65, 2003 | |
Thur, Apr. 30th | Locality sensitive hashing | Munagala | Project reports due |