CS/SE 6301.008.18S — Special Topics in Computer Science — Computational Geometry

Spring 2018
Tuesdays and Thursdays 11:30am–12:45pm
Location: FO 1.502

Jump to Schedule and Homework.

Instructor:

Kyle Fox
Office: ECSS 2.701
Phone: (972) 883-4168
Email: kyle.fox@utdallas.edu
Office Hours: Mondays 2:00pm–3:00pm (enter my office through the ECS Student Services suite ECSS 2.502, walk all the way to the back, and turn right into the hallway just before exiting the suite)
Homepage: https://utdallas.edu/~kyle.fox/

Administrivia:

Required Textbook: Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry—Algorithms and Applications—Third Edition. Spring 2008 (3Marks)
Recommended Lecture Notes: David M. Mount: Computational Geometry

About this course
Class projects
Course syllabus

Announcements

May 21: Homework solutions have been removed from the website in case I want to reuse some questions in future semesters.
May 10: I believe your grades have been posted. Thank you all for a great semester and congrats to those graduating!
April 28: I won't be in the office this Monday, April 30th, so I'm moving office hours to 2:00pm, Tuesday, May 1st. If you would like to meet but that time does not work for you, please send me an email. Thanks!
April 27: I hope everyone has had a great semester! As a reminder, project reports are due on eLearning by Thursday, May 3rd. See the course projects page for more details.

And please remember to submit course evaluations.
April 16: Project presentations begin tomorrow, April 17th! Please remember, you have 18 minutes from setup to tear down so we can get through the presentations before the semester ends. Feel free to use either the white board or your computer. I will try to bring some adapters to help attach USB-C ports to the projector. I cannot guarantee I will have adapters for other kinds of ports.

Also, Homework 4 solutions are now available and grades are in.
March 26: Homework 3 solutions are now available and grades are in. Scores are out of 10, because I only graded Problem 2. Problem 1 has been replaced with 10 points extra credit for everybody as promised.
March 22: Homework 4 has been released. It is due on eLearning by 11:30am on Thursday, April 5th.
March 19: Homework 3 Problem 1 is far more difficult than I anticipated, and the solution I had in mind is incorrect! I apologize. To make up for it, you do not need to write a solution for Problem 1, and I'm give everybody 10 homework points worth of extra credit for the problem. I will set grade boundaries before taking extra credit into account, so this can only help everybody's grade. Sorry again.
March 9: I have posted project proposals to the eLearning Course Homepage. If you share common interests, you are strongly encouraged to work together on your final projects.
March 6: Homework 3 has been released. It is due on eLearning by 11:30am on Thursday, March 22nd.
March 1: Homework 2 has been graded, and solutions are available.

One piece of feedback: When designing algorithms or programming in general, you are strongly encouraged to use reductions. Many of you tried to present incorrect incremental construction algorithms for some of the parts of Problem 1. However, the homework more-or-less told you to just write an LP and explain why solving it leads to a correct solution. Once you know you have a correct LP, you can just call an LP solver like the one from class, and then you have a fully correct answer without worrying about additional details.

The same advice applies for solving Problem 3 (b), not writing your own content management system, not rolling your own crypto, etc. Unless you're trying to improve upon it in some way, it's generally better to rely on somebody else's known correct work than to try doing it again and risk making additional mistakes.
February 16: Grades for Homework 1 are up, and solutions are available. As mentioned Thursday in class, I'm extending the deadline for Homework 2 to Thursday, February 22nd to make up for the late feedback on Homework 1.

Two pieces of feedback: If you work closely with other students, then feel free to submit a single common solution set that includes all of your names (max three students per solution set). You must also cite students you worked with but didn't include in your solution set. Second, you must explain or prove why your algorithms are correct. Doing so will help me understand your algorithm if you do something unexpected, and it will help you to know before submission if what you propose is actually correct.
January 29: As announced in class on Thursday, I will be moving office hours to Monday afternoons at 2pm. I will hold the first of these Monday office hours today, but I will also hold office hours at 2pm tomorrow, Tuesday the 30th due to late notice of the change. Starting next week, regular office hours will be Monday only, or by appointment.
January 26: As announced in class on Tuesday, Homework 1 has been released. It is due on eLearning by 11:30am on Tuesday, February 6th. If you wish to typeset your homework solutions, you may find this template useful.
January 2: Welcome to CS/SE 6301.008.18S — Special Topics in Computer Science — Computational Geometry! All announcements, homework assignments, etc. will be done through this website. Please stay tuned.

Schedule and Homework

Lectures take place Tuesdays and Thursdays from 11:30am to 12:45pm in FO 1.502.

The schedule below will be updated with new subjects and recommended readings throughout the semester. Exact topics discussed in each lecture may change. 3Marks refers to de Berg et al. Mount refers to David M. Mount's online lecture notes . Numbers refer to the relevant chapters or sections.

I am also linking to my notes for lecture in case you find them useful. Caveat emptor! These are basically scripts I wrote for myself, so they may be buggy or incomplete.

Date	Subject/Event	Reading	Notes
Tue, Jan. 9th	Introduction and administrivia, convex hulls, simplifying assumptions, modified Graham's scan [Graham '72, Andrew '79]	3Marks Preface, 1; Mount 1, 3; lecture notes
Thur, Jan. 11th	More convex hulls, lower bound, Jarvis's march (gift wrapping) ['73], output sensitivity, Chan's algorithm ['96]	Mount 4; lecture notes
Tue, Jan. 16th	Line segment intersection, plane sweep [Bentley, Ottmann '79]	3Marks 2–2.1; Mount 5; lecture notes
Thur, Jan. 18th	(Monotone) polygon triangulation [Garey et al. '78], doubly-connected edge lists	3Marks 3; Mount 6; lecture notes
Tue, Jan. 23rd	Monotone polygon decomposition [Lee, Preparata '77] (for triangulation), halfplane intersection, point-line duality	3Marks 3.2, 4.2, 8.2, 11.4; Mount 6, 7; lecture notes	Homework 1 released.
Thur, Jan. 25th	Halfplane intersection and point-line duality continued, linear programming, randomized incremental construction [Seidel '91]	3Marks 4, 11.4; Mount 8; lecture notes
Tue, Jan. 30th	Linear programming and backward analysis for randomized incremental construction, orthogonal range searching via kd-trees	3Marks 5–5.2; Mount 31; lecture notes
Thur, Feb. 1st	Orthogonal range searching continued, kd-trees, orthogonal range trees	3Marks 5; Mount 31–32; lecture notes
Tue, Feb. 6th	Trapezoidal maps, their construction [Mulmuley '90; Seidel '91]; lecture notes	3Marks 6; Mount 9	Homework 1 due (solutions). Homework 2 released.
Thur, Feb. 8th	Trapezoidal maps continued, planar point location, tail bounds (bonus) [Mulmuley '90; Seidel '91]; lecture notes	3Marks 6; Mount 10
Tue, Feb. 13th	Voronoi diagrams, Fortune's algorithm ['87]	3Marks 7–7.2; Mount 11; lecture notes
Thur, Feb. 15th	Delaunay triangulations, uses and properties	3Marks 9–9.2; Mount 12; lecture notes
Tue, Feb. 20th	Delaunay triangulations, randomized incremental construction	3Marks 9.3–9.4; Mount 13; lecture notes
Thur, Feb. 22nd	Line arrangements, construction, zone theorem	3Marks 8.3; Mount 14; lecture notes	Homework 2 due (solutions).
Tue, Feb. 27th	Line arrangement applications, sorting angular sequences, narrowest k-corridor, halfplane discrepancy, plane sweeps	3Marks 8; Mount 15; lecture notes
Thur, Mar. 1st	Delaunay triangulations and 3D lower convex hulls, Voronoi diagrams and 3D upper envelopes	3Marks 11.0, 11.5; Mount 16; lecture notes	See 3Marks 11.1–11.3 for an algorithm to construct 3D convex hulls.
Tue, Mar. 6th	Robot motion planning, configuration spaces, Minkowski sums	3Marks 13; Mount 20; lecture notes	Project proposals due. Homework 3 released.
Thur, Mar. 8th	Robot motion planning continued, visibility graphs, shortest paths	3Marks 15; Mount 29; lecture notes
Tue, Mar. 13th	No class; enjoy Spring Break!
Thur, Mar. 15th	No class; enjoy Spring Break!
Tue, Mar. 20th	Curve similarity, Hausdorff distance, Fréchet distance	Lecture notes
Thur, Mar. 22nd	Approximation algorithms, k-center	Erickson 31.2, 31.8–31.9; lecture notes	Homework 3 due (solutions). Homework 4 released.
Tue, Mar. 27th	Well separated pair decompositions (WSPDs), construction of WSPDs	Mount 17; lecture notes
Thur, Mar. 29th	Applications of WSPDs	Mount 18; lecture notes
Tue, Apr. 3rd	Geometric sampling, VC-dimension	Mount 19; lecture notes
Thur, Apr. 5th	Geometric sampling continued, learning a shape, geometric set cover and hitting set	Mount 19; lecture notes	Homework 4 due (solutions).
Tue, Apr. 10th	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; lecture notes
Thur, Apr. 12th	Locality sensitive hashing	Munagala; lecture notes
Tue, Apr. 17th	Project presentations
Thur, Apr. 19th	More project presentations
Tue, Apr. 24th	Yet more project presentations
Thur, Apr. 26th	Project presentations, course evaluations
Tue, May 1st	Good luck on your finals!
Thur, May 3rd	You're almost done!		Project reports due.