alubiw@uwaterloo.ca, DC 2334, (519) 888-4567, ext. 34449

**Contents:**
Organization,
Course Outline,
Assignments,
Resources,
Lectures,
Project,
Presentation Schedule

- The written project will be due Monday Dec. 12.
- There will be no lecture on Tuesday Nov. 8. The lecture on Thursday Nov. 10 will be given by Professor Timothy Chan on the topic of range searching.
- Oct. 15. Project info is available above.
- Announcements will be posted on Piazza
- Classes start on Tuesday September 13.

**Time and Place:** Tuesday and Thursday,
1:00 -- 2:20 pm. DC 2568.

**Credit:**

- 6 small assignments (1 or 2 questions each) (50%)
- a project (50%). Pick some topic that interests you and is relevant to the course; explore some aspect of it; read a few papers; and survey them. You must do a written report and a class presentation. I will suggest possible topics. NEW: Project deatils available above.

Due |
||

Assignment 1 [pdf] | Tuesday Sept. 27 | |

Assignment 2 [pdf] | Tuesday Oct. 4 | |

Assignment 3 [pdf] | Tuesday Oct. 18 | |

Assignment 4 [pdf] | Tuesday Oct. 25 | |

Assignment 5 [pdf] | Tuesday Nov. 8 | |

Assignment 6 [pdf] | Tuesday Nov. 22 |

**Topics:**

- polygon triangulation
- convex hulls
- Voronoi diagrams and Delaunay triangulations
- arrangements and duality
- linear programming
- geometric data structures, search problems
- motion planning, shortest paths

- [CG]
*Computational Geometry: Algorithms and Applications,*(third edition) M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Springer, 2008.

There should be copies in the bookstore. - [CGinC]
*Computational Geometry in C*(second edition), J. O'Rourke, Cambridge University Press 1998. - [D&CG]
*Discrete and Computational Geometry,*Satyan L. Devadoss and Joseph O'Rourke, Princeton University Press, 2011.

- the computational geometry pages from MathWorld
- CGAL Computational Geometry Algorithms Library
- David Eppstein's Geometry Junkyard and Geometry in Action
- Joseph O'Rourke's comp.graphics.algorithms FAQ
- Graphics Gems

- Computing Research Repository for Computational Geometry (arXiv)
- Google Scholar
- Computational Geometry journals
- Discrete and Computational Geometry
- Computational Geometry Theory and Applications
- Journal of Computational Geometry
- International Journal of Computational Geometry

- Computational Geometry conferences
- Symposium on Computational Geometry
- Canadian Conference on Computational Geometry
- European Symposium on Computational Geometry
- Fall Workshop on Computational Geometry (no proceedings)

- ACM Digital Library

L01 | Tu Sep 13 | slides | Every polygon can be triangulated. The Art Gallery Theorem. | [CG] 3.1. [CGinC] 1.1, 1.2. [D&CG] 1.1 - 1.3. |

L02 | Th Sep 15 | slides | O(n log n) time triangulation algorithm via trapezoidization. | [CG] 3.2, 3.3 (slightly different algorithm). [CGinC] 2.1 - 2.4. |

Also the idea of randomized trapezoidization. | [CGinC] 7.11.4. [CG] 6.2. Seidel's paper | |||

L03 | Tu Sep 20 | slides | Partitioning polygonal regions and polyhedra. | [CGinC] 2.5. Chazelle's paper Bern and Eppstein |

L04 | Th Sep 22 | slides | Convex Hull in the Plane | [CGinC] 3. [CG] 1.1. Chan's paper |

L05 | Tu Sep 27 | slides | Convex Hull in Dimension d | [CGinC] 4. [CG] 11. |

L06 | Th Sep 29 | slides | More on Convex Hull - randomized incremental algorithm | [CGinC] 4. [CG] 11. Seidel's paper |

L07 | Tu Oct 4 | slides | Linear Programming | [CG] 4. Understanding and Using Linear Programming a short basic book on linear programming |

L08 | Th Oct 6 | slides | Voronoi diagrams and Delaunay triangulations | [CGinC] ch. 5.[CG] ch. 7, 9. [D&CG] ch. 4. |

L09 | Th Oct 13 | slides | Voronoi diagrams and Delaunay triangulations, continued | same as above |

L10 | Tu Oct 18 | slides | Delaunay triangulations, continued | same as above. Better presentation of incremental algorithm. |

L11 | Th Oct 20 | slides | Triangulations | refs. in slides. Also Bern-Eppstein survey |

L12 | Tu Oct 25 | slides | Triangulations, continued | refs. in slides. |

L13 | Th Oct 27 | slides | Line Arrangements | [CGinC] ch. 6. [CG] ch. 8. |

L14 | Tu Nov 1 | slides | Planar Point Location | [CGinC] section 7.10 and 7.11. [CG] ch. 6 and section 10.3. |

L15 | Th Nov 3 | slides | Shortest Paths | [CGinC] section 8.2. [CG] chapter 15. |

L16 | Th Nov 10 | Range Searching (Timothy Chan) | [CG] chapter 5. | |

L17 | Tu Nov 15 | slides | Motion Planning | [CGinC] chapter 8. [CG] chapter 13. |

L18 | Th Nov 17 | see L17 | Motion Planning, continued. Plus student presentations. | |

L19 | Tu Nov 22 | student presentations | ||

L20 | Th Nov 24 | student presentations | ||

L21 | Tu Nov 29 | student presentations | ||

L22 | Th Dec 1 | student presentations | ||

L19 | Tu Nov 22 | student presentations |

Tuesday November 22: Zachary, Sean, Brandon, William

Thursday November 24: Armin, Jeremy, Ellen, Alexei

Tuesday November 29: Sebastian, Kshitij, Kewei, Pak Hay

Thursday December 1: Jade, Shayan, Yuan, Corey