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 15-minute presentation about their project; the schedule will be fixed in class.

- Assignment 1 is due October 16, in class.
- Assignment 2 is due November 6, in class.
- Assignment 3 is due December 4, in class.

- 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.

- September 25:
- Linear programming, Chapter 4 in the textbook.
- Euler's formula for planar graphs.
- the Sylvester-Gallai theorem.

- October 2:
- Crossing number of graphs.
- Point-line incidences.
- unit distances.
- Here and here are the notes.
- Point location in planar subdivisions. Here are the notes.
- Point location using persistent trees.

- October 9: Thanksgiving
- October 16:
- Point location in planar subdivisions. Here are the notes.
- Range trees: Chapter 5 in the textbook.

- October 30:
- Range trees and fractional cascading; Chapter 5 in the textbook.
- Art Gallery Problems: Chapter 3 in the textbook.

- November 6:
- Plane sweep.
- Computing intersections in a set of horizontal and vertical line segments.
- the Bentley-Ottmann algorithm.
- Computing intersections in a set of line segments: the Bentley-Ottmann algorithm.
- Classroom examples of robustness problems in geometric computations.
- LEDA.
- CGAL: Computational Geometry Algorithms Library.

- November 13:
- Voronoi diagrams.
- Here are the notes on Voronoi diagrams.
- VoroGlide: an applet to play with Voronoi diagrams.
- An animation.

- November 20:
- Delaunay triangulations and 3D convex hulls.
- Lower envelopes and Davenport-Schinzel sequences.
- Here are my notes.
- The Ackermann function.
- More on the Ackermann function; this function is slightly different from the one we saw in class.

- November 27:
- December 4:
- Friday December 8: Student presentations, 15 minutes per student. You can connect your laptop to the computer in the classroom. You can also bring a USB stick and upload your file to the computer in the classroom.

**Important dates:****End of reading week:**Your project proposal must have been submitted to me.**December 15:**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.