COMP 163/MATH 181

Computational Geometry

Fall 2022

 

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, 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. ]

PREREQUISITE: Computer Science 160 or a 100+ level Mathematics Course or Graduate Standing.

Schedule: MW, 9:00-10:15AM [R+ block]: JCC 140

Class # 1: Wednesday, September 7: Introductions; Upper and Lower Bounds for Convex Hull  
...
Class # 2: Monday, September 12: Gift-Wrapping, Graham's Scan, Incremental, Divide & Conquer .
Class # 3: Wednesday, September 14: Recap of Convex Hull Algorithms. Discussion of Data Structures. Quick Hull. Group Problem Solving.
Class # 4: Monday, September 19: Introduce Dynamic Convex Hulls (and "Order Decomposable Problems"). "Ultimate" algorithm for Convex Hull (and "Prune and Search" paradigm) .
Class # 5: Wednesday, September 21: Complete the discussion and proof of the $O(\log ^2 n)$ updates in the dynamic convex hull algorithm. Continued the discussion of Order Decomposable Problems.
Friday, September 23: First homework due at 11:59pm covering classes 1-4
Class # 6: Monday, September 26: Point inclusion with convex, monotone, and simple polygons. Computing the intersection points of an arrangement of lines in sorted order using line sweep.
Class # 7: Wednesday, September 28: Sweepline algorithm for line segment intersection. Regularizing planar subdivisions.
Class # 8: Monday, October 3: Reviewed regularizing planar subdivisions. Introduce Doubly-Connected-Edge-Lists (DCEL) as well as Quad Edge Data Structures. Detecting and Computing Intersections of Convex Polygons.
Class # 9: Wednesday, October 5: Planar Point Location
Friday, October 7: Second homework due at 11:59pm covering classes 5-8
Monday, October 10: UNIVERSITY HOLIDAY
Class #10: Wednesday, October 12: Duality and Least Median of Squares Regression using Vertical Line Sweep
Class #11: Monday, October 17: Recap and continuation of LMS Regression with Vertical Line Sweep and Introduction to Topological Line Sweep
Class #12: Wednesday, October 19: Topological Line Sweep
Friday, October 21: Third homework due at 11:59pm covering classes 9-12
Class #13: Monday, October 24: 1st test. Augmentations due 36 hours later.
...
Class #14: Wednesday, October 26: Voronoi Diagrams and Continuation of Topological Sweep
Class #15: Monday, October 31: Voronoi Diagrams
Class #16: Wednesday, November 2:
Friday, November 4: Fourth homework due at 11:59pm covering classes 14-16
Class #17: Monday, November 7:
Class #18: Wednesday, November 9:
Class #19: Monday, November 14:
Class #20: Wednesday, November 16: Convex Hulls in Higher Dimensions
Friday, November 18: Fifth Homework Due at 11:59pm covering classes 17-20
Class #21: Monday, November 21: Linear Programming
Class #22: Monday, November 28: Geometric Data Structures
Class #23: Wednesday, November 30: Rectilinear Computational Geometry
Class #24: Monday, December 5: TBA
Class #25: Wednesday, December 7:
Friday, December 9: Sixth Homework Due at 11:59pm covering classes 21-25
Class #26: Monday, December 12: 2nd test. Augmentations due 36 hours later.

Project Presentations (in exam slot): Tuesday, December 20, 8:00-11:00AM
Project materials due by noon on Monday, December 20.
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 Friday, 9/23 at 11:59PM
    • Homework 2 - pdf: Due Friday, 10/7 at 11:59pm
    • Homework 3 - pdf: Due Friday, 10/21 at 11:59pm
    • Homework 4 - pdf: Due Friday, 11/4 at 11:59pm
    • Homework 5 - pdf: Due Friday, 11/18 (or Tuesday, 11/22) at 11:59pm
    • Homework 6 - pdf: Due Friday, 12/9 at 11:59pm

Staff

 

Instructor:

Diane L. Souvaine
JCC 440E
Diane (dot) Souvaine (at) tufts (dot) edu
Office Hours: Mondays, 2-3:3pm and Wednesdays, 12:30-1:30pm
and http://www.cs.tufts.edu/~dls/advising.php
and by appointment

Teaching Assistants:


Jake (dot) Sturim (at) tufts (dot) edu
Office Hours: Fridays, 9-10:30AM

 

 

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.

 

 

 

Resources

 

 

 

Demos

 

 

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

Cinderella

How to run Cinderella

Other computational Geometry

 

 

 

 

LATEX

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

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