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

Spring 2020
Tuesdays and Thursdays 11:30am–12:45pm
Location: ECSN 2.110

## Instructor:

Kyle Fox
Office: ECSS 4.224
Phone: (972) 883-4168
Email: kyle.fox@utdallas.edu
Office Hours: Mondays 10:00am–11:00am and Tuesdays 2:00pm–3:00pm (tentative)
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

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