CSCI5010: Practical Computational Geometry Algorithms Spring 2024 Professor: Yufei Tao TA: Ru Wang Quick links: [Time, Venue, and Zoom Links][Lecture Notes][Exercises]

Brief Description

This course will discuss data structures and algorithms for solving (with strong theoretical guarantees) fundamental geometry problems of low dimensions. Topics covered include convex hulls, maxima, planesweep, polygon triangulation, linear programming, minimum enclosing circle, point location, voronoi diagrams, delaunay triangulation, closest pair, orthogonal range searching, and so on.

Announcements

2. (10 Jan) Exercise List 1 released. There will be no announcements about exercise releases. Please check this website periodicaly. 1. (7 Jan) Hello all.

Time, Venue, and Zoom Links

Monday 2:30pm - 4:15pm, Institute of Chin Studies L1, Zoom Link Tuesday 2:30pm - 3:15pm, William M W Mong Eng Bldg LT, Zoom Link

Grading Scheme

Quiz 1: 10% Quiz 2: 10% Quiz 3: 10% Midterm: 25% Final Exam: 45% Style of Exams: During this course, the instructor will gradually generate a list of exercises with no solutions given. In the midterm and final exams, about 35% of the marks will come from problems taken directly from that list. The rest 65%, however, will be from new problems. In the midterm and the final exams, you will be allowed to bring in a single-sided, A4-sized, note sheet on which you can print/write anything you deem useful.

Textbook and Lecture Notes

The instructor recommends the following textbook: M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Book ownership is optional. The following lecture notes contain most of the course's content: Lecture Notes (thanks to Dave Mount). Additional material will be provided by the instructor. Lecture 0: Computation Model (video) Lecture 1: Planesweep 1 - Segment Intersection Reading: Pg 24-32 of Dave's notes; Sec 2.1 of the textbook. (video 1) (video 2, start - 00:33) Lecture 2: Planesweep 2 - Convex Hulls Reading: Pg 7-15 of Dave's notes; Chapter 1 of the textbook. (video, 00:33 - 01:08) Lecture 3: Planesweep 3 - Polygon Triangulation Reading: Pg 32-39 of Dave's notes; Chapter 3 of the textbook. (video 1, 01:08 - end) (The 2nd video of the lecture was not captured successfully. Be reminded that video releases are 'bonus' rather a guaranteed provision.) (video 3, start - 00:29) Lecture 4: Dimension Reduction 1 - Dominance Screening (video, 00:29 - 01:07) Lecture 5: Dimension Reduction 2 - Rectangle-Point Containment (video, 01:07 - end) Lecture 6: Output-Sensitive Maxima [The following schedule is tentative and may change depending on our progress] Lecture 7: Grid 1 - Closest Pairs Lecture 8: Grid 2 - Well-Separated Pair Decomposition Lecture 9: Grid 3 - Epsilon-Kernels Lecture 10: Point-Plane Duality Lecture 11: Planar Graph 1: Point Location Lecture 12: Planar Graph 2: Voronoi Diagram and Delaunay Triangulation Lecture 13: Backward Analysis 1: Linear Programming Lecture 14: Backward Analysis 2: Minimum Enclosing Discs Lecture 15: Backward Analysis 3: Computing Delaunay Triangulation Lecture 16: VC-Dimensions, Epsilon-Nets, and Epsilon-Approximations Lecture 17: Shallow Cuttings

Exercises

Some midterm/final exam problems will be taken directly from the exercise lists below. No solutions to these exercises will be given. You are free to look for the solutions in any way. Remember: during the exams, you will be allowed to consult only one piece of single-sided A4-sized paper. Exercise List 1 Exercise List 2