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

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

Jump to Schedule and Homework.


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)

About this course
About course projects
Writing policies and advice
Course syllabus


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