Computational Geometry - CS 6/76110

Spring 2025

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 01/29/2025

- remaining problems are due on 02/05/2025

2. Problems (pdf).

- first 3 problems for MS students

- all 4 problems for PhD students

- first two problems are due on 02/12/2025

- remaining problems are due on 02/24/2025

---

EXAMS

---

1. Midterm Exam, Wednesday, March 5, 2025, 12:30 am - 1:45 pm overview

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

---

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

---

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.