|
COMP 163/MATH 163 Computational Geometry Spring 2011 |
|
|
Announcements |
- NOTE THE CHANGES to the Schedule below. In particular, the class on
Monday, March 28 will be led by Andrew Winslow and will include strategizing
solutions for Homework 4, which is due on Wednesday, March 30. ALSO, on Wednesday,
March 30, we will have a "double class" running from 10:30AM - 1:20PM with pizza.
- During the semester, announcements will be listed here, with
dates.
- Guidelines for submitting homework solutions ps, pdf
- Lecture Notes
- Geometric software (including LEDA) resources
- Midterm 1 Solutions
|
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.
|
Schedule |
First classes: Monday 1/24 and Wednesday 1/26, 10:30-11:45AM
Special Class: Thursday 1/27, 9:00-10:15AM
No classes: Monday 1/31 and Wednesday 2/2.
Regular Class: Monday 2/7 (HW due) and Wednesday 2/9, 10:30-11:45AM
Special Class: Wednesday 2/9, 12:00-1:15PM (right after regular class) with pizza at 11:45AM
No classes: Monday 2/14 and Wednesday 2/16
Regular Class: Monday 2/21 (HW due) and Wednesday 2/23, 10:30-11:45AM
Special Class: Wednesday 2/23, 12:00-1:15PM (right after regular class) with pizza at 11:45AM
Regular Class: Monday 2/28 and Wednesday 3/2, 10:30-11:45AM
Regular Class: Monday 3/7 (HW due) and Wednesday 3/9, 10:30-11:45AM
First Written Exam:In class: Monday, March 14, 10:30-11:45am; Take Home Revisions due: Wednesday, March 16, 10:30am.
VACATION: Week of March 20-27.
Class Period on Monday, March 28 will involve group strategizing on Homework 4
Special Class: Wednesday March 30, 12:00-1:15PM (right after regular class) with pizza at 11:45AM
Homeworks 4-6 due on Wednesdays, March 30, April 13, April 27. Second Written Exam: Monday, May 2, 10:30-11:45am.
Project Presentations/"Oral Exam": Thursday, May 12, 11:30 - 2:30 pm (with pizza).
Please submit projects on-line by 11:59pm on Wednesday, May 11.
|
Homework |
This list will be created during the
semester.
Instructor:Diane L. Souvaine |
Teaching Assistant:Andrew Winslow
|
Co-Teaching Assistants:Anjulika Gupta and Constantin Berzan
|
|
TextBooks and References |
|
|
Required textbook |
|
|
Joseph
O'Rourke |
|
|
Franco P. Preparata,
Michael Ian Shamos |
|
|
Jean-Daniel
Boissonnat, Mariette Yvinec, Translated by H. Bronniman |
|
|
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 |
|
|
D. L. Souvaine Lecture Notes in Computational Geometry, 1997. |
|
|
Ketan
Mulmuley |
|
|
|
|
Resources |
|
|
|
|
|
Demos |
|
|
|
Construction of 3D convex
hull, incremental algorithm Michael Horn , Sweep line
Voronoi construction developed at the Delaunay Triangulations, Voronoi Diagrams and Gabriel Graphs developed by Takashi Ohyama Graham's
Scan developed at Quickhull
developed at 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 Quadtrees (a spatial data
structure) by Frantisek Brabec and Hanan Samet from the
List of Computational Geometry Demos maintained by Jeff Erickson, |
|
|
|
|
|
|
|
|
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 |
|
|
|
|
|
|
|
|
Documentation of LEDA book (Thanks to Cory McMahon) |
|
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) |
|
Document Preparation with Latex, by Budgen and Nelson. (Excellent) Getting Started with Latex, by Wilkins. (Shorter but good for getting started) |