COMP 163/MATH 181

Computational Geometry

Fall 2025

 

Announcements
  • During the semester, announcements will be listed here (or possibly in Canvas or in Piazza), with dates.
  • Homework will be submitted over Gradescope. Here are draft guidelines for submitting homework solutions: pdf
  • LATEX template, tex format, ps and pdf. See also LATEX resources.

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: Six written homework assignments due at 11:59pm on alternate Thursdays, occasional spontaneous quizzes, two tests (where you have the option of augmenting your answers up to 30 hours later),and an implementation/theory project.

PREREQUISITE: CS 160 or CS 170 or a 100+ level Mathematics Course or Graduate Standing and some pertinent prior background.

Schedule: MW, 1:30-2:45 [G+ block]: Lane 100

Class # 1: Wednesday, September 3: Introductions; Upper and Lower Bounds for Convex Hulls  
Class # 2: Monday, September 8: Additional Convex Hull Algorithms: Jarvis March, Graham's Scan, Incremental, Divide & Conquer .
Class # 3: Wednesday, September 10: Recap of Convex Hull Algorithms. Discussion of Data Structures. Dynamic Convex Hull. Group Problem Solving.
Class # 4: Monday, September 15: Point inclusion in Convex Polygons and Simple Polygons, Quick Hull, Dynamic Convex Hulls (an "Order Decomposable Problem"). Begin "Ultimate" algorithm
Class # 5: Wednesday, September 17: "Ultimate" algorithm for Convex Hull (and "Prune and Search" paradigm). Brief introduction to line segment intersection..

Thursday, September 18: First homework due at 11:59pm covering classes 1-4

Class # 6: Monday, September 22: Sweepline algorithm for line segment intersection. Point inclusion with convex, monotone, and simple polygons.
Class # 7: Wednesday, September 24: Sweepline algorithm for line segment intersection. Regularizing planar subdivisions. Introduce Doubly-Connected-Edge-Lists (DCEL) as well as Quad Edge Data Structures.
Class # 8: Monday, September 29: Detecting and Computing Intersections of Convex Polygons. Compute the intersection points of n lines in sorted order. Joint Problem Solving
Class # 9: Wednesday, October 1: Triangulating a Monotone Polygon, Planar Point Location

Thursday, October 2: Second homework due at 11:59pm covering classes 5-8

Class #10: Monday, October 6: Duality and Least Median of Squares Regression using Vertical Line Sweep
Class #11: Wednesday, October 8: Recap and continuation of LMS Regression with Vertical Line Sweep and Introduction to Topological Line Sweep. Double Wedges
Monday, October 13: UNIVERSITY HOLIDAY
Class #12: Wednesday, October 15: Topological Line Sweep

Thursday, October 16: Third homework due at 11:59pm covering classes 9-12

Class #13: Monday, October 20: 1st test. Augmentations due Tuesday, October 21 at 11:59pm.

Class #14: Wednesday, October 22: Voronoi Diagrams
Class #15: Monday, October 27: Voronoi Diagrams
Class #16: Wednesday, October 29: Review Sweepline Algorithm and begin Convex Hulls in Higher Dimensions

Thursday, October 30: Fourth homework due at 11:59pm covering classes 14-16
Class #17: Monday, November 3: Convex Hulls in Higher Dimensions
Class #18: Wednesday, November 5: Convex Hulls in Higher Dimensions
Class #19: Monday, November 10: Convex Hulls in Higher Dimensions
Class #20: Wednesday, November 12: Convex Hulls in Higher Dimensions

Thursday, November 13: Fifth Homework Due at 11:59pm covering classes 17-20
Class #21: Monday, November 17: Rectilinear Computational Geometry
Class #22: Wednesday, November 19: Geometric Data Structures
Class #23: Monday, November 24: Linear Programming

Thursday, December 4: Sixth Homework Due at 11:59pm covering classes 21-25

Class #26: Monday, December 8: 2nd test. Augmentations due Tuesday, December 9, 11:59pm.

Project Presentations (in exam slot): Friday, December 12, 11:30am - 3:00pm (pizza lunch provided).
Project materials due by 11:59pm on Thursday, December 11.
Login to the Tufts CS machines and type "provide cs163 project file1 file2 ..." at the prompt.

Homework

This list will be created during the semester. I expect there to be six (6) homeworks, with one due roughly every two weeks, and a final project.

    • Homework 1 - pdf: Due Thursday, 9/18 at 11:59PM
    • Homework 2 - pdf: Due Thursday, 10/2 at 11:59pm
    • Homework 3 - pdf: Thursday, 10/16 at 11:59pm
    • Homework 4 - pdf: Due Thursday, 10/30 at 11:59pm
    • Homework 5 - pdf: Due Thursday, 11/13 at 11:59pm
    • Homework 6 - pdf: Due Thursday, 12/4 at 11:59pm
    • Project - pdf

Staff

 

Instructor:

Diane L. Souvaine
JCC 440E
Diane (dot) Souvaine (at) tufts (dot) edu
Office Hours: Mondays, 11am-12noon, JCC 440E
Wednesdays, 3-4pm EXCEPT for 9/24 and 11/19, JCC 440E
Wednesday, 9/24 ONLY: 12:15-1:15, Packard 201

https://tufts.zoom.us/my/dsouvaine.
http://www.cs.tufts.edu/~dls/advising.php
.

Course Assistants:

Matt Jones
mjones05 (at) cs (dot) tufts (dot) edu
Office Hours: Thursdays, 1:00-3:00pm; TTC 117 on 10/2 & 10/9; Halligan 118 on all other days.


Saskia Solotko
Saskia (dot) Solotko (at) tufts (dot) edu
Office Hours:
Tuesdays (weeks with HW due), 2:00-4:00, JCC 652 except for 11/11 which is a holiday.

 

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 2005, revised.

 

D. L. Souvaine

Lecture Notes in Computational Geometry, 2022f: Lecture Notes 2022f.

 

D.L. Souvaine; I. Bjorling-Sachs

The contour problem for restricted-orientation polygons: link to paper.

 

 

 

Resources: TBA

 

 

 

Demos

 

Fortune's Algorithm Visualization, by Vladimir Porokhin (project for CS163 in Fall 2017)

 

Latex

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

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