Computational Geometry - CS 6/76110

Spring 2021

MW 5:30 pm - 6:45 pm     
Remote

Office hours (Remote this semester): MW 6:45 - 7:45 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

Presentations by students:   Schedule

Some Geometric Algorithms and Software Available on the Web:

• CGAL: Computational Geometry Algorithms Library (in C++) 
• Toussant's Geometric Link to many other sites, including those on animation of geometric algorithms. 
• An Applet of Graham's scan (Convex Hull Algorithm)
• Qhull-- Qhull implements the QuickHull algorithm for computing the convex hull.
• An Applet on Voronoi Diagram and Delaunay Triangulation

Textbook:  Computational Geometry:  an Introduction, Springer-Verlag, 1993 (5th printing) by F.P. Preparata,  and M.I. Shamos

---

HOMEWORKS 

---

1. Problems (pdf). (Distributed 01/??/2021, Due 02/??/2021)

- first two problems for MS students

- all three problems for PhD students

2. Problems (pdf). (Distributed 02/??/2021, Due 03/??/2021)

- first 3 problems for MS students

- all 4 problems for PhD students

---

EXAMS

---

1. Midterm Exam, ?????day, March ??, 2021, 5:30 - 6:45 pm

2. Final Exam, Monday, May 10, 2021, 5:45 - 8:00 pm

---

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

---

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.