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.
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.
|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; lecture notes||3Marks 4.4, 6–6.1; Mount 8, 9||Homework 1 due 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||Homework 2 due February 21st|
|Thur, Mar. 12th||Project proposals due|
|Tue, Mar. 17th||No class; enjoy your Spring break!|
|Thur, Mar. 19th||No class; enjoy your Spring break!|
|Thur, Apr. 30th||Project reports due|