# CS 6301.002.20S — Special Topics in Computer Science — Computational Geometry

Spring 2020
Tuesdays and Thursdays 11:30am–12:45pm
Live lectures (starting March 31): WebEx seminar. Link will be given on eLearning.
Recorded lectures: Posted on YouTube as soon as they are available. See Schedule and Homework for links to videos.

## Instructor:

Kyle Fox
Office: ECSS 4.224
Phone: (972) 883-4168
Email: kyle.fox@utdallas.edu
Office Hours: Tuesdays 2:00pm–3:00pm and Thursdays 10:00am–11:00am on WebEx
Homepage: https://personal.utdallas.edu/~kyle.fox/

Nicely Typeset Electronic Notes: David M. Mount: CMSC 754—Computational Geometry
Textbook: Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry—Algorithms and Applications—Third Edition. Springer 2008 (3Marks)

Course syllabus

## Announcements

• 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.

1. Lectures will now take place fully online. Those who can are encouraged to attend a live lecture on WebEx. The meeting link will be emailed to everybody at least 12 hours in advance of each lecture. As soon as possible after the lecture completes, a recording will be uploaded to YouTube. Links to the YouTube recordings will be added to the schedule below. Please do not ask any questions during the live lecture you do not wish to become public until after we are done recording.
2. Office hours will also be done using WebEx in Kyle's personal WebEx meeting room. Due to work and childcare conflicts, Monday office hours have been moved to Thursdays from 10:00am to 11:00am. We can break out for private conversations or schedule other meeting times by request.
3. Most of our lives have been disrupted quite a bit lately, so the policy for late work has been relaxed. Please try to make the posted deadlines, but also do not be afraid to tell Kyle if you need a little extra time to finish your work at no penalty.

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.

1. The deadline for project proposals has been extended to Friday, March 20th. You are encouraged not to resubmit and instead take your break if you already have a submission you are happy with.
2. We will have one more homework assignment that will likely have three questions. It will likely be released Friday, April 3rd (after the extended break is over) and be due three weeks later on Friday, April 24th.
3. As of right now, project reports are still due the last day of classes, Thursday, April 30th. Kyle will see if what university rules have to say about extending this deadline into the next week.

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.

## Schedule and Homework

The schedule below will be updated with new subjects and recommended readings throughout the semester. Exact topics discussed in each lecture may change.

Shortly before or after each lecture, I will update the readings with my own notes/script. Use at your own risk! I make improvements every semester, but my notes likely have typos or maybe even a few bugs!
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