|
CSCI5010: Practical Computational Geometry Algorithms Spring 2021 Professor: Yufei Tao TA: Shangqi Lu Quick links: [Zoom Links][Lecture Notes][Exercises] |
| Brief Description |
|
This course will discuss data structures and algorithms for solving with good theoretical guarantees fundamental geometry problems that have significant importance in computer science. 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 |
|
21. (28 Apr) The Zoom link for the final exam is https://cuhk.zoom.us/j/94990226997. 20. (20 Apr) Exercise list 12 released. 19. (13 Apr) Exercise list 11 released. 18. (31 Mar) Quiz 3 will take place in the lecture of Apr 12. The scope covers Topics 10-11. The questions will be released at the beginning of the quiz. You need to submit your solutions to the Blackboard system within 15 minutes. 17. (31 Mar) Exercise list 10 released. 16. (28 Mar) Exercise list 9 released. 15. (16 Mar) Quiz 2 will take place in the lecture of Mar 22. The scope covers Topics 8-9. The questions will be released at the beginning of the quiz. You need to submit your solutions to the Blackboard system within 15 minutes. 14. (16 Mar) Exercise list 8 released. 13. (9 Mar) Exercise list 7 released. 12. (1 Mar) The midterm exam will take place in the lecture of 9 Mar. The scope covers everything in Topics 1-7 and Exercise Lists 1-6. The questions will be released at the beginning of the exam. You need to submit your solutions to the Blackboard system within 45 minutes. 11. (1 Mar) Exercise list 6 released. 10. (9 Feb) The final exam will be held on Apr 29, from 3pm to 5pm. 9. (9 Feb) Exercise list 5 released. 8. (26 Jan) Exercise list 4 released. 7. (1 Feb) Quiz 1 will take place in the lecture of Feb 8 (Week 5). The scope covers everything in Topics 1-3. The questions will be released at the beginning of the quiz. You need to submit your solutions to the Blackboard system within 15 minutes. 6. (1 Feb) The tentative schedule of the quizzes and the midterm:
4. (25 Jan) Exercise list 2 released. 3. (19 Jan) Exercise list 1 released. 2. (11 Jan) Today's lecture and whiteboard picture have been uploaded to the Blackboard system. There will be no future announcements about such uploads. Please check the system after each lecture. 1. (10 Jan) Hello all. |
| Time and Zoom Links |
|
Monday 10:30am - 12:15pm, Zoom Link Tuesday 10:30am - 11:15pm, Zoom Link |
| Grading Scheme |
|
Quiz 1: 10% Quiz 2: 10% Quiz 3: 10% Midterm: 25% Final Exam: 45% |
| 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. Topic 0: Computation Model Topic 1: Convex Hulls Reading: Lec 3 of Dave's notes. Extra reading: Textbook Chapter 1. Topic 2: Output-Sensitive Maxima Topic 3: Planesweep 1 - Segment Intersection Reading: Lec 5 of Dave's notes. Extra reading: Sec 2.1 of the textbook. Topic 4: Planesweep 2 - Polygon Triangulation Reading: Lec 6 of Dave's notes. Extra reading: Chapter 3 of the textbook. Topic 5: Dimensionality Reduction 1 - Maxima Topic 6: Dimensionality Reduction 2 - Rectangle-Point Containment Old version of the notes (changes: see Slides 4, 10, and 11 of the new version) Topic 7: Point Location Reading: Lec 26 of Dave's notes. Topic 8: Backward Analysis 1 - Linear Programming Reading: Lec 7 of Dave's notes. Extra reading: Sec 4.1-4.6 of the textbook. Topic 9: Backward Analysis 2 - Minimum Enclosing Disc Extra reading: Lec 23 of Dave's notes and Sec 4.7 of the textbook. Old version of the lecture notes (error: Lemma 3 statement) Topic 10: Voronoi Diagram (and Nearest Neighbor Search) Reading: Lec 11 of Dave's notes (you may ignore the planesweep algorithm). Extra reading: Sec 7.1 of the textbook. Topic 11: Backward Analysis 3 - Delaunay Triangulation Reading: Lec 12-13 of Dave's notes. Extra reading: Sections 9.1-9.4 of the textbook. Topic 12: Grid Decomposition - Closest and Close Pairs Extra reading: Lec 33 of Dave's notes. Topic 13: Point-Plane Duality and Line Arrangements Reading: Lec 2, 8, 14, and 15 of Dave's notes. Extra reading: Chapter 8 of the textbook. There will be no more lectures. |
| Exercises |
|
Some midterm/final exam problems will be taken almost directly from the exercise lists below. No solutions to these exercises will be given. You, however, are welcome to present your solutions to the instructor; he will tell you whether the solutions are correct. Exercise List 1 Exercise List 2 Exercise List 3 Exercise List 4 Exercise List 5 Exercise List 6 Exercise List 7 Exercise List 8 Exercise List 9 Exercise List 10 Exercise List 11 Exercise List 12 There will be no more exercises. |
|
|