CSCI5010: Computational Geometry Algorithms 15-29 July 2019 Professor: Yufei Tao

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

5. (Jul 30) Assignment 2 has been released. 4. (Jul 20) Assignment 1 has been released. Please scroll to the bottom of the page to see it. 3. (Jul 15) The final exam will be held on the afternoon of Jul 29 (Mon), from 2pm to 4pm. 2. (Jul 15) The midterm exam will be held on the afternoon of Jul 22 (Mon), from 2pm to 4pm. 1. (Jul 14) Hello all.

Time and Venues

Every working day from July 15 to July 29: Morning: 9am - 11:30am Afternoon: 2pm - 3:45pm Venue: Room 604, Yifu Building, Fudan University

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: Trapezoidal Maps and Point Location. Reading: Lec 9-10 of Dave's notes. Extra reading: Chapter 6 of the textbook. Topic 8: 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 9: Point-Plane Duality. Reading: Lec 2 and 8 of Dave's notes. Extra reading: Sec 8.2 of the textbook. Topic 10: Orthogonal Range Reporting. Reading: Lec 16-17 of Dave's notes. Extra reading: Sec 5.1-5.5 and Sec 10.2 of the textbook. Topic 11: Grid Decomposition. Reading: Instructor's slides. Extra reading: Lec 33 of Dave's notes.

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 Exercise List 6 Exercise List 7 Exercise List 8 Exercise List 9 Exercise List 10 Exercise List 11 Exercise List 12 Exercise List 13 (Not testable)

Assignments

Assignment 1: Click here to download. Each student is expected to submit a pdf describing her/his solutions. The pdf should be emailed to the instructor at taoyf@cse.cuhk.edu.hk. The deadline is 11:59pm, 7 Aug. Assignment 2: Click here to download. Each student is expected to submit a pdf describing her/his solutions. The pdf should be emailed to the instructor at taoyf@cse.cuhk.edu.hk. The deadline is 11:59pm, 7 Aug.