COMP 163/MATH 163 Computational Geometry Spring 2008

Announcements

• During the semester, announcements will be listed here, with dates.
• Guidelines for submitting homework solutions ps, pdf
• Lecture Notes
• Geometric software (including LEDA) 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. 

PREREQUISITE: Computer Science 160 or consent.

Tentative Schedule

First Class: Wednesday, January 16, 3:00-4:15 p.m., Halligan 111B  
NO CLASS on Monday, January 20.
First Exam: In class: Monday, March 10, 3:00-4:15 pm; Take Home Revisions due: Wednesday, March 12, 3:00 p.m.
Last Homework Due: Monday, April 28
Projects Due: Monday, April 28
Final Exam: Tuesday, May 6, 12:00-2:00 p.m.

Homework

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
• Homework 7 - pdf
• Homework 8 - pdf
• Homework 9 - pdf
• Homework 10 - pdf

Staff

Instructor: Diane L. Souvaine Halligan 102 dls (at) cs (dot) tufts (dot) edu Office Hours: 4:15-5:00pm on Mondays & 2:00-2:45 p.m. on Wednesdays and by appointment

Teaching Assistants: Mashhood Ishaque mishaq01 (at) cs (dot) tufts (dot) edu Office Hours: 1:30-3:00 p.m. on Mondays and Tuesdays, and by appointment

TextBooks and References

	Required textbook Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf Computational Geometry: Algorithms and Applications Springer-Verlag, second edition, 2000.
	Joseph O'Rourke Computational Geometry in C Cambridge University Press, second edition, 1998
	Franco P. Preparata, Michael Ian Shamos Computational Geometry Springer-Verlag, corrected fifth printing, 1993
	Jean-Daniel Boissonnat, Mariette Yvinec, Translated by H. Bronniman Algorithmic Geometry Cambridge University press2002
	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.
	Herbert Edelsbrunner Algorithms in Combinatorial Geometry EATCS Monographs on Theoretical Computer Science, Vol. 10 Springer-Verlag, 1987
	D. L. Souvaine Lecture Notes in Computational Geometry, 1997.
	Ketan Mulmuley Computational Geometry: An Introduction Through Randomized Algorithms Prentice-Hall, 1993

Resources
Demos
	Construction of 3D convex hull, incremental algorithm Michael Horn , Tufts University Sweep line Voronoi construction developed at the University of Copenhagen by Allan Odgaard and Benny Kjaer Nielsen Delaunay Triangulations, Voronoi Diagrams and Gabriel Graphs developed by Takashi Ohyama Graham's Scan developed at Princeton University by Hausner and Dobkin Quickhull developed at Princeton University by Hausner and Dobkin. VoroGlide animating Voronoi diagrams, developed in Rolf Kleins former group at Fernuniversität Hagen Rotating Calipers Examples of problems that can be solved using rotating calipers, developed by Hormoz Pirzadeh from Mcgill university 3D animation of convex hull algorithms: incremental, gift-wrap, divide-and-conquer and quickhull. Developed by Tim Lambert from the university of New South Wales, Australia Quadtrees (a spatial data structure) by Frantisek Brabec and Hanan Samet from the University of Maryland List of Computational Geometry Demos maintained by Jeff Erickson, UIUC
Papers and Web Information
	This list will grow throughout the the semester. Convex Hulls from Godfried T. Toussaint's web page. A History of Linear-time Convex Hull Algorithms for Simple Polygons by Greg Aloupis “Topologically Sweeping the Complete Graph in Optimal Time and Space" , E. Rafalin, D. Souvaine, Tufts CS Technical Report, 2003-05 "Topological Sweep in Degenerate cases", E. Rafalin, D. Souvaine, I. Streinu, Proceedings of the 4th international workshop on Algorithm Engineering and Experiments, ALENEX 02, in LNCS 2409, Springer-Verlag, Berlin, Germany, pages 155-156, Postscript version, Pdf version "Topologically Sweeping an arrangement", H.Edelsbrunner, L. Guibas, J. of Computer and System Sciences 38, 165-194, 1989
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
	Computational Geometry Lecture notes, by Stefan Schirra Computational Geometry Lectures by Dave Mount Computational Geometry Pages by Jeff Erickson (including interactive software) Computational Geometry on the web by Godfried T. Toussaint (including software)
LATEX	Document Preparation with Latex, by Budgen and Nelson. (Excellent) Getting Started with Latex, by Wilkins. (Shorter but good for getting started)