COMP 163/MATH 181

Computational Geometry

Fall 2023

 

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, an implementation/theory project, and scribing for 2 classes.
[When ready to submit notes, Login to the Tufts CS machines and type "provide cs163 classnotes file1 file2 ..." at the prompt, submitting both the pdf and the LaTex as well as any image files. Please use a filename that references the dates when the classes were scribed.]

Thursday, September 21: First homework due at 11:59pm covering classes 1-4
Thursday, October 5: Second homework due at 11:59pm covering classes 5-8
Thursday, October 19: Third homework due at 11:59pm covering classes 9-12
Class #13: Monday, October 23: 1st test. Augmentations due Tuesday, October 24 at 11:59pm.
Thursday, November 2: Fourth homework due at 11:59pm covering classes 14-16
Thursday, November 16: Fifth Homework Due at 11:59pm covering classes 17-20
Thursday, December 7: Sixth Homework Due at 11:59pm covering classes 21-25
Class #26: Monday, December 11: 2nd test. Augmentations due Tuesday, December 12, 11:59pm.

Project Presentations (in exam slot): Thursday, December 14, 3:15-5:30PM
Project materials due by noon on Thursday, December 14.
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/21 at 11:59PM
    • Homework 2 - pdf: Due Thursday, 10/5 at 11:59pm
    • Homework 3 - pdf: Thursday, 10/19 at 11:59pm
    • Homework 4 - pdf: Due Thursday, 11/2 at 11:59pm
    • Homework 5 - pdf: Due Thursday, 11/16 at 11:59pm
    • Homework 6 - pdf: Due Friday, 12/8 at 11:59pm

Staff

 

Instructor:

Diane L. Souvaine
JCC 440E
Diane (dot) Souvaine (at) tufts (dot) edu
Office Hours: Tuesday, 1:30-3:00pm and 5:00-5:30pm, Zoom at https://tufts.zoom.us/my/dsouvaine.
and http://www.cs.tufts.edu/~dls/advising.php
.

Course Assistants:

Alex Bai
Alexander (dot) Bai (at) tufts (dot) edu
Office Hours: Tuesdays, 7:30-8:45pm; JCC 235


Saskia Solotko
Saskia (dot) Solotko (at) tufts (dot) edu
Office Hours: Thursdays, 12:30-2:00pm; JCC 442

 

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)