Computational Geometry - CS 6/76110

Fall 2013

TR  5:30 pm - 6:45 pm     
MSB   115

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:

• 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.
• Incremental, Gift Wrap, Divide and Conquer, QuickHull
• QuickHull
• The Voronoi Web Site
• An Applet on Voronoi Diagram and Delaunay Triangulation
• A Delaunay Triangulation demonstration

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

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

---

HOMEWORKS 

---

1. Problems (pdf). (Distributed 9/10/13, Due 10/03/2013)

- first 2 problems for MS students

- all 3 problems for PhD students

2. Problems (pdf). (Distributed 10/01/13, Due 10/22/2013)

- first 3 problems for MS students

- all 4 problems for PhD students

Grader: Muad Abu-Ata

Office hours: Th. 3 - 5 pm (room 253)

---

EXAMS

---

1. Thursday, October 24, 2013, 5:30 - 6:45 p.m. {Chapters with the following topics: Geometric Searching; Point Location; Convex Hulls: Algorithms; Convex Hulls: Applications}

- Overview is on Tuesday, October 22, 2013

2. Tuesday, December 10, 2013, 5:45 - 8:00 p.m. {Chapters with the following topics: Proximity: Fundamental Algorithms; Proximity: Variants and Applications; CG in Wireless Networks: first two class presentations}

- Overview is on Thursday, December 5, 2013

---

F. F. Dragan
dragan at cs dot kent dot edu
Fall 2013

---

NOTICE OF MY COPYRIGHT AND INTELLECTUAL PROPERTY RIGHTS. Any intellectual property displayed or distributed to students during this course (including but not limited to powerpoint presentations, notes, quizzes, examinations) by the professor remains the intellectual property of the professor. This means that the student may not distribute, publish or provide such intellectual property to any other person or entity for any reason, commercial or otherwise, without the express written permission of the professor.