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/

Administrivia:

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

Announcements


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