CSCI5010: Practical Computational Geometry Algorithms

Spring 2014

Professor: Yufei Tao
TA: Xiaocheng Hu

Brief Description

This course will discuss data structures and algorithms for solving fundamental problems in computational geometry with good theoretical guarantees. Topics covered include line-segment intersection, polygon triangulation, convex hull, linear programming, orthogonal range searching, point location, voronoi diagram, delaunay triangulation, and so on.

Announcements

1. (Jan 9) Exercise list 1 released.
2. (Jan 17) Exercise list 2 released.
3. (Jan 21) Exercise list 3 released.
4. (Feb 6) Exercise list 4 released.
5. (Feb 15) Exercise list 5 released.
6. (Feb 15) Midterm will be held in the lecture of Mar 3. The scope includes everything from Lectures 1-5. The exam is open book. Its duration is 60 minutes.
7. (Feb 15) Assignment 1: Write down your solution to Problem 2 of Exercise List 3, and send your solution to the TA by Feb 22 (i.e., a week from now). You may assume you have a solution to Problem 1 of Exercise List 3.
8. (Feb 17) Exercise list 6 released.
9. (Feb 28) Your assignment 1 is ready for collection from the TA.
10. (Mar 1) Excercise list 7 released.
11. (Mar 9) You may approach the TA to inspect your midterm paper. After the inspection, please return the paper to the TA.
12. (Mar 10) Excercise list 8 released.
13. (Mar 15) Excercise list 9 released.
14. (Mar 22) Excercise list 10 released.
15. (Mar 22) There will be no lecture on Mar 31 because the instructor will be on conference leave. The lecture will be rescheduled, and the details will be announced later.
16. (Mar 22) Assignment 2: Write down your solution to Problem 2 of Exercise List 9, and send your solution to the TA by Mar 30 (i.e., a week from now).
17. (Mar 27) Excercise list 11 released.
18. (Apr 4) There will be makeup lecture on Apr 8 (Tue). The time is from 6:30pm to 9:30pm; and the classroom is ERB 408.
19. (Apr 4) The final exam will be held from 7pm to 9pm on Apr 28 in ERB 804.
20. (Apr 14) Excercise list 12 released.

Time and Venues

Lecture
Mon 11:30am - 2:15pm G06, Y.C. Liang Hall

Grading Scheme

Attendance: 15%
Assignments: 25%
Midterm: 25%
Final Exam: 35%

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.

Lecture Notes (thanks to Dave Mount).

Lecture 1: Preliminaries, and Convex Hull.
Reading: Pages 1-9 (of Dave's notes).

Lecture 2: Maxima
Reading: My notes.

Lecture 3: Planesweep, and Subdivision.
Reading: Pages 13-20.

Lecture 4: DCEL and Polygon Triangulation.
Reading: Pages 21-31.

Lecture 5: Halfplane Intersection, Duality, and Linear Programming.
Reading: Pages 31-42.

Lecture 6: Minimum Enclosing Disc, and kd-Tree.
Reading: My notes; Pages 42-45 of Dave's notes.

Lecture 7: Range Tree, and Fractional Cascading.
Reading: Pages 46-48.

Lecture 8: Midterm, Interval Tree, and Priority Search Tree.
Reading: My notes

Lecture 9: Improved Range Tree, and Kirkpatrick's Algorithm.
Reading: Pages 49-53.

Lecture 10: Trapezoidal Map, and Segment Intersection (Revisited).
Reading: Pages 53-60, and 99-103.

Lecture 11: Voronoi Diagram.
Reading: Pages 61-69.

Lecture 12: Delaunay Triangulation.
Reading: Pages 69-74.

Lecture 13: Delaunay Triangulation 2, and Arrangements.
Reading: Pages 74-77, and 82-84.

Lecture 14: Miknowski Sum and Motion Planning.
Reading: Pages 88-92, and 94-97.

Exercises and Exams

Some final exam problems will be taken directly from the exercise lists below. No solution 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 (Updated on Apr 14)
Exercise List 8
Exercise List 9
Exercise List 10
Exercise List 11
Exercise List 12

Midterm
Final