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, and an implementation/theory project.

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

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

Class #1: Wednesday, September 7: Upper and Lower Bounds for Convex Hull

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.

Staff

Instructor: Diane L. Souvaine JCC 440E Diane (dot) Souvaine (at) tufts (dot) edu Office Hours: TBA and http://www.cs.tufts.edu/~dls/advising.php

Teaching Assistants: Jonathan (dot) Conroy (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.

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)