Fall 2017

- Convex hull algorithms
- Triangulations of point sets
- Euler's formula for planar graphs, with applications
- The k-set problem
- Point location in planar subdivisions
- Multi-level data structures (range trees, segment trees, interval trees, priority search trees)
- Plane sweep algorithms
- Voronoi diagrams and Delaunay triangulations
- Lower envelopes and Davenport-Schinzel sequences
- Computing the diameter of a point set
- Algorithms for geometric optimization problems
- Triangulations of polygons

- The course will mainly be based on lecture notes which will be posted on this page.
- Some chapters from the following book will be covered:

Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Computational Geometry, Algorithms and Applications, 3rd edition, Springer-Verlag, 2008. This book is available online through the Carleton library.

**3 Assignments (50%).****Project (40%).**The project can either be (i) an implementation (with documentation) of a geometric algorithm, or (ii) a survey paper about a specific topic in computational geometry.**Project Presentation (10%).**Each student will make a XXX-minute presentation about their project; the schedule will be fixed in class.

- Will be posted here.

- September 11: Computing the
convex hull of a planar point set.
- Here are the notes.

- September 18:
- More on convex hulls, intersection of halfplanes, point-line duality, from the notes above.
- Introduction to linear programming, Chapter 4 in the textbook.

**Important dates:****End of reading week:**Your project proposal must have been submitted to me.**XXX:**Deadline for project submission.

- You are welcome to come up with any interesting topic that has a strong geometric content.
- Write software that visualizes (and explains) an algorithm that we have seen in class.
- Implement one of the algorithms that we have seen in class and do experiments on large inputs.
- Take one of the topics that we have seen in class or is in the textbook, and write a survey about other results that are known for this topic.
- The Delaunay triangulation shows up in many application areas (including non-computer-science areas). Write a survey on how and why the Delaunay triangulation is used.
- Write a survey on algorithms for the point location problem in planar graphs.
- Write a survey on nearest-neighbor searching.
- Write software that visualizes (and explains) the duality transform between points and lines, and the relationship between the intersection of halfplanes and convex hulls.
- Write a survey on Art Gallery Theorems.
- Write a survey on facility location problems.
- Implement several convex hull algorithms (such as Gift Wrapping and Graham's Scan) and compare the running time in different scenarios.
- Implement Kirkpatrick's data structure for point location and do experiments on large planar graphs.
- Write a survey on hidden-surface removal algorithms.
- Implement and experiment with range trees.
- Implement Voronoi diagram and Delaunay triangulation.
- Implement and visualize k-d trees and quad trees.