Computational Geometry - CS 6/76110

MW  05:30 pm - 06:45 pm

MSB 276

Topics	Chapters
Introduction	1.1-1.2.3 and 1.3.1
Geometric Searching	2.1 and 2.3-2.3.2
Point Location	2.2-2.2.2.2 and 1.2.3.2
Convex Hulls: Algorithms	3.1-3.3.6
Convex Hulls: Applications	4.1.2 and 4.2
Proximity: Fundamental Algorithms	5.1-5.6
Proximity: Variants and Applications	6.1 and 6.4
CG in Wireless Networks	Survey1 Survey2
Intersections	7.1 and 7.2

Presentations by students:  

1. MS Students
2. PhD Students

Geometric Algorithms and Software Available on the Web:

• A comprehensive collection of geometric software 
• CGAL: Computational Geometry Algorithms Library (in C++) 
• LEDA: Library of Efficient Datatypes and Algorithms (in C++) 
• The Stony Brook Algorithm Repository: Implementation in C, C++, Pascal and Fortran 
• Toussant's Geometric Link to many other sites, including those on animation of geometric algorithms. 
• An Applet of Line Sweeping Algorithm
• An Applet of Graham's scan (Convex Hull Algorithm)
• Qhull-- Qhull implements the QuickHull algorithm for computing the convex hull.
• Graham Scan and Gift Wrapping
• QuickHull
• The Voronoi Web Site
• An Applet on Voronoi Diagram and Delaunay Triangulation
• A Delaunay Triangulation demonstration
• An interactive applet with convex hull, Delaunay triangulation and Voronoi diagram.

Textbook:  Computational Geometry:  an Introduction, Springer-Verlag, 1993 (5th printing)

by F.P. Preparata,  and M.I. Shamos

---

HOMEWORKS 

---

1. Problems (pdf). (Distributed 1/26/11, Due 2/16/2011) results
2. Problems (pdf). (Distributed 2/16/11, Due 3/09/2011) results

---

EXAMS

---

1. Monday, March 14, 2011, 5:30 - 6:45 p.m. {Chapters from the following topics: Geometric Searching; Point Location; Convex Hulls: Algorithms; Convex Hulls: Applications}   results
2. Monday, May 2, 2011, 5:45 - 8:00 p.m.

---

F. F. Dragan
dragan at cs dot kent dot edu
Spring 2011