Examples of topics covered (see the Resources page for more details)

• 2D convex hulls
  • (the shortest path surrounding a point set or polygon)
• triangulations
  • (subdividing a polygon into triangles),
• art gallery problems
  • (placing cameras to guard a museum)
• farthest/closest pair
  • (what two points are nearest neighbors?)
• minimum enclosing objects
  • (e.g., bounding boxes)
• range searching
  • (finding how many data points fall inside a given query box)
• intersection problems
  • (e.g., counting intersections among rectangles)
• point location
  • (determining where you are on a map)
• Voronoi diagrams
  • (finding which customer regions belong to a set of vendors)
• combinatorial geometry
  • (exploring patterns and properties of point sets and lines)
• data depth
  • (defining and computing the center of a data set; where to place a hospital)
• the ham-sandwich theorem
  • (how to fairly divide a 2-topping pizza, or a ham-and-cheese sandwich, with a single cut)
• the Borsuk-Ulam theorem
  • (a proof that there are always two points on opposite sides of the planet, with equal temperature and equal pressure)

• What really matters:
  • To succeed in this class, you should already understand or be able to quickly catch up on the following:
    • big-O notation
    • basic data structures such as linked lists, arrays, stacks, balanced binary search trees
    • divide and conquer, recursion, solving recurrence relations (with big-O flexibility)
    • proof by induction / contradiction
  • We will use certain algorithmic concepts as tools, without needing to know how they work: e.g., sorting, selection (median-finding).
  • Some topics in this course have a difficulty level comparable to an introductory Algorithms course. Others are more sophisticated, so prior experience with an Algorithms course is preferred.
  • See the Resources page for more details on what prerequisites are needed for each topic encountered in this course.
  • Programming is not required for assignments. We focus on how to think before coding.
  • Programming experience can be useful for the project. Students often choose to implement or create a demo for an algorithm. Theory projects are also accepted.
• Official prerequisite:
  • Algorithms: CS-3000 or CS-5800 or equivalent. Exceptions can be made; see below.
  • Students may request special permission to take this course, if they will not have the opportunity to take it in a following year. In this case, they must have done well in data structures and discrete math, demonstrate suitable mathematical maturity, and be willing to fill in the gaps along the way. My algorithms notes can help with this. Please contact me if you haven't taken Algorithms but want to try this course.

• Two exams; one halfway through the semester and the other on the last day or during the final exam period. Non-cumulative. Each worth 20%.
• One project, involving description, visualization, presentation, and/or implementation of a computational geometry algorithm. (Possibly a course topic that needs a refreshed demo. Possibly some more advanced extension, or part of a published paper). Depending on enrolment, there might be an option to form small teams. Worth 30%.
• Homework assignments, worth 25%. Subject to enrolment, homework might be done in a collaborative way, involving a lot of instructor guidance and multiple revisions until students get to final solutions.
• Participation, worth 5%. There are many ways to satisfy this part. It is somewhat informal.

• Copies of lecture notes and online links will be provided. The following books are not required, but might be helpful.
• Computational Geometry: Algorithms and Applications, by de Berg, van Kreveld, Overmars, Schwarzkopf.
  This is the most commonly used textbook for intro to Comp.Geom.
• Computational Geometry in C, by Joseph O'Rourke

Everyone involved in this course is to respect the following:

• Northeastern academic integrity policy
• Northeastern equal opportunity, non-discrimination, non-harassment policy
• Code of Student Conduct
• Basically, be nice.

• The slightest form of academic dishonesty on homework, exams or project will result in an F in the course and a report to administration.
• It is not acceptable to copy solutions from any source or to distribute or receive solutions.

Disability Resource Center:

• If you are student with a disability who is requesting accommodations, please see the information in this link:
  Northeastern DRC