Computational Geometry - CS 6/76110

Spring 2026

MW 12:30 pm - 1:45 pm, MSB Room 121
Office hours: MW 1:45 pm - 3: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 

Description: Description: Description: Description: Description: Description: image002

 

 

 

HOMEWORKS 

  1. Problems (pdf).

-          first two problems for MS students

-          all three problems for PhD students

-          first problem is due 02/04/2026

-          remaining problems are due on 02/09/2026

  1. Problems (pdf).

-          first 3 problems for MS students

-          all 4 problems for PhD students

-          first two problems are due on 02/18/2026

-          remaining problems are due on 02/23/2026

 

EXAMS

1.      Midterm Exam, Monday, March 2, 2026, 12:30 pm - 1:45 pm overview

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

 

 


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

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.