Computational Geometry - CS 6/76110

Spring 2016

MW 12:30 pm - 01:45 pm     
MSB - 276

Office hours: MW 3:30 - 5:00 PM or by appointment

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

Programming Projects: MS Students

Projects are due on April 15 midnight (submit a pointer to google-doc directory containing an executable file and zipped source files).

Coding Project presentations are on April 25, 2016, 12:30 pm - 01:45 pm

Presentations by students:   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 2/1/16, Due 2/15/2016)

- first two problems for MS students

- all three problems for PhD students

2. Problems (pdf). (Distributed 2/17/16, Due 3/07/2016)

- first 3 problems for MS students

- all 4 problems for PhD students

---

EXAMS

---

1. Midterm Exam, Monday, March 14, 2016, 12:30 pm - 01:45 pm

2. Final Exam, Tuesday, May 10, 2016, 10:15 - 12:30 p.m.

---

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

---

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.