Presentations by students:  

1. Introduction: Geometry Structures in Wireless Networks, Spanners, Localized Algorithms (1-2.4) (BHADURI, SUDIPTA) 
2. Simple Topologies: RNG, GG, Yao-Graphs and Bounded Degree Topologies (3-3.2.3) (FUHRY, DAVID P)
3. Planar Spanners and Delaunay Graphs (3.3-3.3.3) (JADHAV, RAJESH NANDKUMAR)
4. Bounded Degree Planar Spanners: Centralized and Localized Construction (3.4-3.4.2) (XIANG, YANG)
5. Transmission Power Control; Clustering, Virtual Backbone: Centralized Methods (3.6-4.1) (PANKAJ, AMITABH K)
6. Clustering, Virtual Backbone: Distributed Methods (4.2-4.2.3) (VIYYURE, UDAYKIRAN VARMA)
7. Localized Routings  (5-5.3) (SINGARAJU, PRASAD DV)
8. Computational Geometry in BioInformatics - overview (STOFFER, DEBORAH ANN) (examples include docking and folding problems, scoring protein structures using Delaunay tetrahedralization, 3-D Protein matching, 3-D (molecular) Surface Representation, Extraction of Geometrical and Biological (3-D Motion) invariant indices, etc.; e.g., see http://biogeometry.duke.edu/,  http://helix-web.stanford.edu/psb05/intro-biogeometry.pdf, http://biogeometry.duke.edu/education/,                http://bioinfo3d.cs.tau.ac.il/Education/CS99b/bio-course.html,  http://www.fastlane.nsf.gov/servlet/showaward?award=0086013, http://www4.nas.edu/pga/rap.nsf/ByTitle/AE.00.00.B6189?OpenDocument, http://cgi.ncsa.uiuc.edu/cgi-bin/General/CC/irg/clearing/projectAbstract.pl?projid=1754, etc…..

Geometric Algorithms and Softwares 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
• An Applet on Voronoi Diagram and Delaunay Triangulation 
• A Delaunay Triangulation demonstration

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

1. Problems (pdf). (Due 2/28/2006) 
2. Problems (pdf). (Due 4/04/2006) 
3. Problems (pdf). (Due 5/02/2006) 

1. Tuesday, March 21, 2006, 12:30 - 1:45 p.m.   
2. Tuesday, May 9, 2006,  12:45 - 3:00 pm