Winter Semester 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 February 10, in class.
- Assignment 2 is due March 3, in class.
- Assignment 3 is due March 17, in class.

- January 6: Computing the
convex hull of a planar point set.
- Here are the notes.

- January 13: More on convex hulls, intersection of halfplanes, point-line duality, from the notes above.
- January 20:
- Euler's formula for planar graphs.
- crossing number.
- the Sylvester-Gallai theorem.
- Point-line incidences.
- unit distances.
- Here and here are the notes.

- January 27:
- Point location in planar subdivisions. Here are the notes.
- Point location using persistent trees.
- Range trees: Chapter 5 in the textbook.

- February 3:
- Range trees: Chapter 5 in the textbook.
- 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.

- February 10:
- Voronoi diagrams.
- Here are the notes on Voronoi diagrams.
- VoroGlide: an applet to play with Voronoi diagrams.

- February 17:
- Delaunay triangulations and 3D convex hulls.
- Linear programming, Chapter 4 in the textbook.

- February 24: no class because of reading week.
- March 3:
- March 10: Darryl Hill talked about routing algorithms.
- March 17:
- Lower envelopes and Davenport-Schinzel sequences.
- The Ackermann function.
- More on the Ackermann function; this function is slightly different from the one we saw in class.

- March 24:
- March 31:
- Sink spanners, how to combine them with the Yao-graph to obtain a spanner of bounded degree (Arya, Das, Mount, Salowe, Smid. Euclidean spanners: short, thin, and lanky. Proceedings 27th ACM Symposium on the Theory of Computing (STOC), 1995, pp. 489-498.)
- The Art Gallery Theorem: Chapter 3 in the textbook.

- April 7: 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.**Friday April 21:**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.