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.


Kyle Fox
Office: ECSS 2.701
Phone: (972) 883-4168
Email: [email protected]
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/


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


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.