csci 3250: Computational Geometry, Fall 2024, Bowdoin College

  • Instructor: Laura Toma (she/her)
  • Email: ltoma at bowdoin.edu
  • Office: Searles 219
  • Class time: MW 1:15-2:40
  • Classroom: Searles 126

Prerequisites

csci 2200 (Algorithms) and csci 2330 (Systems). In other words, basic knowledge of:

  • Analysis (asymptotic notation, growth, recurrences); basic algorithms and data structures (searching, sorting, binary search trees, priority queues) and algorithm design techniques (divide-and-conquer, greedy)
  • Programming in C/C++, Unix terminal commands and Makefiles

Overview

Computational geometry studies algorithms for problems that involve geometric data – sets of points, line segments, polygons and polyhedra — and is a field driven by applications in e.g. graphics, robotics and databases.

Examples of geometric problems include: Is a point inside or outside a given polygon? Given a set of points in the plane, what is the closest pair of points? What is the smallest convex polygon that contains a set of points in the plane? Find all the points that fall in a given query range. Find the area that is visible from a point in a polygon. Do two polygons intersect? Given a set of polygonal obstacles and a polygonal robot, find a collision-free paths from a start to an end location.

This class is an introduction to computational geometry and draws from fundamental topics and techniques in the field.

Learning goals

  • Understand fundamental problems and techniques in computational geometry
  • Gain experience implementing geometric algorithms, including designing test cases, handling special “degenerate” inputs, and using visualization
  • Gain experience developing in C/C++ and working on larger projects
  • Experience the importance of efficient algorithms in practice
  • Improve communication and writing skills through presentations and project reports

Syllabus overview

The class will draw from the following set of fundamental topics:

  • Introduction (collinear points, closest pair of points)
  • Geometric primitives (area of triangle, orientation, segment intersection)
  • Convex hulls in 2D (naive, gift wrapping, quickhull, Graham scan, incremental, divide-and-conquer; lower bound)
  • Convex hulls in 3D
  • Segment intersection (Bentley-Ottman sweep)
  • The art gallery problem and Fisk’s sufficiency proof
  • Polygon triangulation (quadratic, based on ear removal algorithm; triangulation of monotone polygons; polygon triangulation in O(n lg n) via trapezoidalization)
  • Geometric searching (orthogonal range searching with kd-trees and range trees)
  • [Voronoi diagrams and Delaunay triangulations]
  • [Duality]
  • Combinatorial motion planning in 2D (C-space and C-obstacles; planning via graph search; visibility graph)
  • Heuristical motion planning (grid-based techniques, sampling, PRM, RRT)

Textbooks

There is no required textbook. The course is based on two classical textbooks, below. You can find them in Searles 224 (you’re more than welcome to check them out but please do not take them out of 224).

Communication

Class communication will be entirely on Slack. You will need to monitor Slack for class updates, including possible cancellations or delays. The link to join Slack is posted on Canvas.

Course requirements and grading policy

  • Projects: 70%
  • Exams: 20%
  • Class engagement: 10%

Projects: We are aiming for 7 projects, due approximately biweekly.

Exams: There will be two exams, a midterm and a final, non-cumulative. Exams will be in class, the first one approximately half way through the semester and the second one at the end of the semester. Exact dates will be announced later.

Engagement: Engagement is crucial for effective learning and as such it counts as a significant part of your grade. Note that engagement does not mean having the right answers. It means contributing to the class learning community.

  • To help engagement: attend class, work with your peers, consistently and independently engage in discussions during class, volunteer ideas and make observations, ask questions, work on the whiteboards, draw diagrams and examples, participate on Slack, attend office hours, be respectful and inclusive of your peers, don’t be loud, have a positive attitude, do your best to have a good time and strive to turn in good work.

  • Activities that hinder the class learning community: doing something else in class (including working on a different assignment), checking your messages, dominating the discussion, not talking at all or talking too much, showing off when you finish a problem fast, not doing your readings and coming unprepared to contribute.