|
CSCI5010: Practical Computational Geometry Algorithms Spring 2018 Professor: Yufei Tao TA: Yuzhe Ma |
||||||||||||
| 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 | ||||||||||||
|
25. (Apr 25) Notes for the final exam: (a) The scope covers all topics. (b) You are permitted to bring in a piece of A4-sized paper. You can print or write anything on one side of the paper. Other than this piece of paper, you will not be allowed to consult any other materials during the exam. (c) 30% of the marks will be from Exercise Lists 1-13. (d) The duration of the exam is 2 hours. It will start at 7pm, May 4. The venue is ERB 404. 24. (Apr 25) Exercise List 13 released. 23. (Apr 19) Exercise List 12 released. 22. (Apr 15) The venue of the final exam (May 4) wll be ERB 404. 21. (Apr 15) The venue of the make-up lecture (Apr 24) wll be ERB 408. 20. (Apr 12) The final exam will be held on the evening of May 4, from 7pm to 10pm. The venue will be announced once ready. 19. (Apr 12) There will be a make-up lecture on the evening of Apr 24, from 7pm to 10pm. The venue will be announced once ready. 18. (Apr 11) Exercise List 11 released. 17. (Apr 11) The project has been released. The deadline is 12 May. 16. (Apr 5) Midterm stats: average = 79.9, and standard deviation = 21. You may now come to the instructor's office to see your papers. 15. (Mar 31) There will be no lectures on Apr 3 (Tue). A make-up lecture will be arranged. 14. (Mar 22) Exercise List 10 released. 13. (Mar 22) The midterm exam will take place next week. There will be two exams, to be held in the Mon's and Tue's lectures, respectively. Here are some notes about the arrangements: (a) The Mon exam has a full mark of 30, and contains 3 problems selected from the exercise lists. The Tue exam has a full mark of 70, and contains 8 new problems. (b) The exams of both days will be open-book. Feel free to bring in anything non-electronic. This means that phones, iPad, and tablets will not be allowed. (c) You can use any results already proved in the class directly. For example, if you want to compute the convex hull of n 2D points, just say "compute the convex hull in O(n log n) time" without having to give any details. (d) You can also use any results stated in the problems of the exercise lists, unless otherwise stated. For example, if you want to use the "general binary search" in Prob 1 of Ex list 2 in dealing with a different problem, you may just say "do the general binary search in O(log n) time (where n is the length of the array)". 12. (Mar 13) Exercise List 9 released. 11. (Mar 8) The scope of the midterm covers everything from Topic 1 to Topic 7. 10. (Mar 8) Exercise List 8 released. 9. (Mar 2) Exercise List 7 released. 8. (Feb 26) Exercise List 6 released. 7. (Feb 5) Exercise List 5 released. 6. (Feb 4) Exercise List 4 released. 5. (Jan 27) Exercise List 3 released. 4. (Jan 23) The midterm exam will be arranged in Week 11, i.e., in the lectures of Mar 26 and 27. 3. (Jan 12) Exercise List 2 released. 2. (Jan 9) Exercise List 1 released. 1. (Jan 7) Hello all. |
||||||||||||
| Time and Venues | ||||||||||||
|
||||||||||||
| Grading Scheme | ||||||||||||
|
Assignments: 25% Midterm: 25% Final Exam: 50% |
||||||||||||
| 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. Springer. Ownership of the book is optional. The following lecture notes contain most of the content of the course: Lecture Notes (thanks to Dave Mount). The course will also cover some material outside the above notes. Such material will be supplied by the instructor. Topic 1: Convex Hulls. Reading: Lec 3 of Dave's notes (Pages 10-15). Extra reading (if a book is owned): Chapter 1 of the textbook. Topic 2: Output-Sensitive Maxima. Reading: Instructor's notes. Topic 3: Planesweep. Reading: Lec 5 of Dave's notes. Extra reading: Sec 2.1 of the textbook. Topic 4: Polygon Triangulation. Reading: Lec 6 of Dave's notes. Extra reading: Chapter 3 of the textbook. Topic 5: Linear Programming. Reading: Lec 7 of Dave's notes. Extra reading: Sec 4.1-4.6 of the textbook. Topic 6: Minimum Enclosing Circle. Reading: Instructor's notes. Extra reading: Lec 23 of Dave's notes, and Sec 4.7 of the textbook. Topic 7: Point-Plane Duality. Reading: Lec 8 of Dave's notes. Extra reading: Sec 8.2 of the textbook. Topic 8: Trapezoidal Maps and Point Location. Reading: Lec 9-10 of Dave's notes. Extra reading: Chapter 6 of the textbook. Topic 9: Voronoi Diagram and Delaunay Triangulation. Reading: Lec 11-13 of Dave's notes (you may ignore the planesweep algorithm in Lec 11 if you want). Extra reading: Sec 7.1 and Sections 9.1-9.4 of the textbook. Topic 10: Grid Decomposition. Reading: Instructor's slides. Extra reading: Lec 33 of Dave's notes. Topic 11: Orthogonal Range Reporting. Reading: Lec 16-17 of Dave's notes (you may ignore fractional cascading). Extra reading: Sec 5.1-5.5 of the textbook. |
||||||||||||
| Exercises | ||||||||||||
|
Some midterm/final exam problems will be taken 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 (if a solution is incorrect, the instructor will explain why). Exercise List 1 Exercise List 2 Exercise List 3 Exercise List 4 Exercise List 5 (corrected on 24 Mar -- the O(n) time remark removed in Problem 4) Exercise List 6 Exercise List 7 Exercise List 8 Exercise List 9 Exercise List 10 Exercise List 11 Exercise List 12 Exercise List 13 |
||||||||||||
|
|