COMP 163: Computational Geometry
Fall 2017

Instructor: Greg Aloupis
office: Halligan 210

gmail : comp163greg     [please do not message me at my Tufts email]

Prerequisites
• What I really care about:
• To succeed in this class, the student will need to already understand, or quickly learn, the following: big-O notation; basic data structures such as linked lists, arrays, stacks, balanced binary search trees; recursion, divide and conquer; proof by induction/contradiction; basic properties and algorithms for graphs.
See the Reading page for more details on what prerequisites are needed for each topic to be covered in this class.
Programming is not required, besides a project that typically involves some implementation, although theory projects are accepted.
• Official prerequisite
• COMP 160. Exceptions can be made; see below.
• Students may contact me requesting special permission to take COMP 163, especially if they will not have the opportunity to take it in a following year. In this case, they must have done well in COMP 15 and 61, or demonstrate suitable mathematical maturity.

Topics: This is a course on algorithms that involve manipulating geometric shapes. It teaches problem-solving in a fun, intuitive, visual manner.

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

• 2D convex hulls
• (the shortest path surrounding a point set or polygon)
• triangulations
• art gallery problems
• (placing cameras to guard a museum)
• farthest/closest pair
• minimum enclosing objects
• range searching
• (finding how many data points fall inside a given query box)
• intersection problems
• point location
• 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
• 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
• (there are always two points on opposite sides of the planet, with equal temperature and equal pressure)

This course will help to prepare students for applications such as VLSI design, computer graphics, robotics, computer-aided design, visualization, pattern recognition, and statistics.