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 algorithmic geometry problems of low dimensions. Topics covered include convex hulls, maxima, polygon triangulation, intersection problems, closest pair, nearest neighbor search, Euclidean mininum spanning trees, ε-kernels, point location, minimum enclosing balls, linear programming, ε-nets, ε-approximations, and so on. We will also cover a set of generic techniques in computational geometry, including planesweep, dimension reduction, output-sensitiveness, grid decomposition, well-separated point decomposition, point-plane duality, backward analysis, etc.

Announcements

News 16 (1 May): You can now see your final exam scores on Blackboard. You can check your papers by making an appointment with the TA by 8 May, 2024. News 15 (12 Apr): The venue of the final exam will be ERB 401. News 14 (10 Apr): You can now see your Quiz 3 scores in Blackboard. You may email the TA to make an appointment to collect your papers. News 13 (28 Mar): The final exam of this course will be held from 7pm to 9pm, Apr 30 (Tue). The venue will be announced later. News 12 (26 Mar): Quiz 3 will take place in the Monday lecture next week (Apr 8). The scope covers Lectures 13-17. News 11 (25 Mar): You can now see your midterm scores in Blackboard. The midterm papers will be returned to you during next Monday's lecture. Alternatively, you may also visit the instructor's office (RM 1019, SHB) to collect your papers; appointments are required. News 10 (5 Mar): New Video Release Policy: The instructor has noticed a growing trend among students who prefer watching lecture videos instead of attending the lectures in person. This undermines the purpose of releasing videos and significantly impacts the classroom teaching atmosphere. Therefore, from now on, lecture videos will be released based on two conditions: (i) successful capture of the video via Zoom, and (ii) attendance of at least 10 students (i.e., 40% of the class) during the lecture. News 9 (5 Mar): There will be no lecture on Apr 2 (Tue). News 8 (5 Mar): The midterm exam will take place in the lecture of Mar 18. The scope covers everything in Lectures 1-13 and Exercise Lists 1-11. In the exam, you can use - without proofs - any result that is stated in the lecture notes and our exercises, unless the proof is explicitly solicited. News 7 (28 Feb): You can now see your Quiz 2 scores in Blackboard. You may email the TA to make an appointment to collect your papers. News 6 (20 Feb): Quiz 2 will take place in the Monday lecture next week (Feb 26). The scope covers Lectures 6-9. News 5 (6 Feb): You can now see your Quiz 1 scores in Blackboard. You may email the TA to make an appointment to collect your papers. News 4 (30 Jan): Quiz 1 will take place in the Monday lecture next week (Feb 5). The scope covers Lectures 1-5. News 3 (23 Jan): Please note the test schedule for this course: Quiz 1 (20 minutes) is to be held in the lecture of Feb 5 (Mon, Week 5); Quiz 2 (20 minutes) in the lecture of Feb 26 (Mon, Week 7); Midterm (90 minutes) is to be held in the lecture of Mar 18 (Mon, Week 10); Quiz 3 (20 minutes) in the lecture of Apr 8 (Mon, Week 12). The quizzes will be open-book, but the midterm exam will follow the "style of exams" explained in the Grading Scheme session of this webpage. News 2 (10 Jan): Exercise List 1 released. There will be no announcements about exercise releases. Please check this website periodicaly. News 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 Prof. 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 Prof. Mount'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 Prof. Mount's notes; Chapter 1 of the textbook. (video, 00:33 - 01:08) Lecture 3: Planesweep 3 - Polygon Triangulation Reading: Pg 32-39 of Prof. Mount'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 If you do not want to work on Exercise List 4, read Pg 17-21 of Prof. Mount's notes. (video) Lecture 7: Grid 1 - Closest Pair (video, start - 00:47) Lecture 8: Grid 2 - Well-Separated Pair Decomposition (WSPD) Reading: Pg 115-123 of Prof. Mount's notes. (video 1, 00:47 - end) (video 2) (video 3) Lecture 9: Grid 2 (cont.) - WSPD Applications: Approximate Diameters, Spanners, and EMST Reading: Pg 123-130 of Prof. Mount's notes. (video) Lecture 10: Grid 3 - ε-Kernels Reading: Pg 130-134 of Prof. Mount's notes. (video) Lecture 11: Point-Line Duality Reading: Pg 39-45 of Prof. Mount's notes; Section 8.2 of the textbook. (video 1) (video 2, start - 00:30) Lecture 12: Line Arrangements Reading: Pg 90-97 of Prof. Mount's notes; Section 8.3 of the textbook. If you want to learn about the DCEL, read Section 2.2 of the textbook. (video 1, 00:30 - end, unfortunately no audio captured after 54:00) (video 2) Lecture 13: Planar Graph 1: Point Location Reading: Pg 173-177 of Prof. Mount's notes. If you want to learn about the trapezoidal map, read Pg 55-56 of Prof. Mount's notes; Section 6.1 of the textbook. (video) Lecture 14: Planar Graph 2: Voronoi Diagram and Delaunay Triangulation (Basic Properties) Reading: Pg 66-68 and 75-81 of Prof. Mount's notes; Sectoin 7.1 of the textbook. (video 1) (video 2) Lecture 15: Backward Analysis 1: The Core (video) Lecture 16: Backward Analysis 2: Linear Programming Reading: Pg 45-55 of Prof. Mount's notes; Chapter 4 of the textbook. (video) Lecture 17: Backward Analysis 3: Minimum Enclosing Balls (video) Lecture 18: Backward Analysis 4: Delaunay Triangulation (Computation) Reading: Proof for "Legality means Delaunay" Reading: Lect 12 of Prof. Mount's notes; Sec 9.3 of the textbook; [optional] Sec 9.4 of the textbook for a complete analysis. (video 1) (video 2) Lecture 19: Range Space 1: VC-Dimensions, ε-Nets, and ε-Approximations Reading: Pg 138-143 of Prof. Mount's notes. (video 1) (video 2) (video 3, start - 00:29) Lecture 20: Range Space 2: Iterative Re-weighting (not testable) Reading: Pg 144-147 of Prof. Mount's notes. (video, 00:29-end) There will be no more lectures.

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 Exercise List 3 Exercise List 4 Exercise List 5 Exercise List 6 Exercise List 7 (this list will not tested) Exercise List 8 Exercise List 9 Exercise List 10 Exercise List 11 Exercise List 12 Exercise List 13 Exercise List 14 Exercise List 15 Exercise List 16 There will be no more exercises.