COMP 163/MATH 163

Computational Geometry

Fall 2018



  • During the semester, announcements will be listed here, with dates.
  • Guidelines for submitting homework solutions pdf
  • Lecture notes on Triangulation and Regularizing Subdivisions pdf

Brief Description

Computational geometry is concerned with the design and analysis of algorithms for solving geometric problems. Applications can be found in such fields as VLSI design, computer graphics, robotics, computer-aided design, pattern recognition, and statistics. The aim of the course will be to introduce some basic problems of computational geometry and discuss algorithms for solving these problems. The ultimate aim will be to identify general paradigms and data structures of particular importance to solving computational geometry problems, and thereby provide the participants with a solid foundation in the field.

Topics Covered: Design and analysis of algorithms for geometric problems. Topics include proof of lower bounds, convex hulls, searching and point location, plane sweep and arrangements of lines, Voronoi diagrams, intersection problems, decomposition and partitioning, farthest-pairs and closest-pairs, rectilinear computational geometry. 

Expected Work: Written homework assignments, a midterm exam, an implementation project, and a final exam.

PREREQUISITE: Computer Science 160 or consent.

Tentative Schedule

First Class: Tuesday, September 4, 9:00-11:30 a.m., Anderson 312  
First Homework Due: Tuesday, 9/18 before class.
NO CLASS: Tuesday, September 25
MAKEUP-CLASS for 9/25: Friday, September 21, 9 - 10:45AM
MAKEUP-CLASS for 9/25: Friday, October 5, 9-10:45am
Second Homework Due: Wednesday, 10/3 by 4:30pm.
Third Homework Due: Wednesday, 10/17 by 4:30pm.
Midterm Exam: Tuesday, 10/23.
Fourth Homework Due: Wednesday, 10/31 by 4:30pm.
Fifth Homework Due: Wednesday, 11/14 by 4:30pm.
Sixth (Last) Homework due: Wednesday, 11/28 by 4:30pm.
Projects Due: Tuesday, December 4, 9:00-11:45 am (last class)
Final Exam: Tuesday, December 18, 11:30-1:30pm.


This list will be created during the semester.

    • Please answer each question on a separate sheet.
    • Homework 1 - pdf
    • Homework 2 - pdf
    • Homework 3 - pdf
    • Homework 4 - pdf
    • Homework 5 - pdf
    • Homework 6 - pdf
    • Project - pdf




Diane L. Souvaine
Halligan 239
dls (at) cs (dot) tufts (dot) edu
Office Hours:
Thursday, 10:30-11:50AM: 9/13,20; 11/1,15; 12/6.
Monday, 2:30-4:00PM: 10/1,15,22,29; 11/5,19,26; 12/3,10,17.
Monday, 9-10AM by appt only: 10/15,22,29; 11/5,19,26; 12/3,10,17.

Teaching Assistants:

Matt Jones
Matthew (dot) Jones (at) tufts (dot) edu
Office Hours: TBA



TextBooks and References


Main textbook
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf
Computational Geometry: Algorithms and Applications
Springer-Verlag, third edition, 2000.

Joseph O'Rourke
Computational Geometry in C
Cambridge University Press, second edition, 1998

Satyan L. Devadoss and Joseph O'Rourke
Discrete and Computational Geometry
Princeton University Press, 2011

Joseph O'Rourke and Csaba Tóth
Handbook of Discrete and Computational Geometry
Princeton University Press, 2017

Franco P. Preparata, Michael Ian Shamos
Computational Geometry
Springer-Verlag, corrected fifth printing, 1993


D. P. Dobkin and D. L. Souvaine, 

Computational Geometry -- A User's Guide.

Chapter 2 of Advances in Robotics 1: Algorithmic and Geometric Aspects of Robotics, J. T. Schwartz and C. K. Yap, eds., Lawrence Erlbaum Associates, 1987, 43-93. User Guide


D. L. Souvaine

Lecture Notes in Computational Geometry, 2005: Lecture Notes.











List of Computational Geometry Demos maintained by Jeff Erickson, UIUC

Papers and Web Information




Geometric Software





LEDA Documentation

Documentation of LEDA book (Thanks to Cory McMahon)

CGAL Documentation

A simple CGAL example (thanks to Ryan Coleman)

Geomview Documentation


How to run Cinderella

Other computational Geometry






Document Preparation with Latex, by Budgen and Nelson. (Excellent)

Getting Started with Latex, by Wilkins. (Shorter but good for getting started)