Computational Geometry - CS 6/76110

Spring 2024

MW 12:30 pm - 1:45 pm, MSB Room 115
Office hours: MW 10:30 am - 12:30 pm or by appointment

Topics (notes)	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: Topics 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.

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

---

HOMEWORKS 

---

1. Problems (pdf).

- first two problems for MS students

- all three problems for PhD students

- first problem is due 02/05/2024

- remaining problems are due on 02/14/2024

2. Problems (pdf).

- first 3 problems for MS students

- all 4 problems for PhD students

- first two problems are due on 02/26/2024

- remaining problems are due on 03/04/2024

---

EXAMS

---

1. Midterm Exam, Monday, March 11, 2024, 12:30 am - 1:45 pm overview

2. Final Exam, Wednesday, May 8, 2024, 10:15 am - 12:30 pm. overview

---

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

---

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.