COMP 163: Computational Geometry
Instructor: Greg Aloupis
office: Halligan 210
gmail : comp163greg [please do not message me at my Tufts email]
- What I really care about:
- To succeed in this class, the student will need to already understand, or
quickly learn, the following:
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
This is a course on algorithms that involve manipulating geometric shapes.
It teaches problem-solving in a fun, intuitive, visual
Examples of topics covered (see the Reading page
for more details)
- 2D convex hulls
- art gallery problems
- (placing cameras to
- 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.
- Two exams; one in mid / end of October in class, and the
other on the last day or during the final exam period.
Each of these will be worth 20%.
- One project, involving description, visualization, and/or
implementation of a research problem in computational geometry. Worth
30%. Possibility to substitute with a presentation.
Homework assignments, worth 25%. (Note: the hw workload will be far less than
Participation, worth 5%.
- 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