CS 478 / CS 564 COMPUTATIONAL GEOMETRY (Spring 2023-2024)

Instructor: Ugur Güdükbay (Room EA-403, Tel: 1386)
Office Hours: Tuesday 13:30-15:30 (EA-403)
Course Schedule: Wednesday 08:30-09.20 (Spare Hour), 09.30-10:20, Friday 13:30-14.20, 14.30-15:20 (EE-04)
Course Assistant: Sinan Sonlu. Please send e-mail for any course related issues and appointment for office hour

Please visit Course Homepage frequently to see the announcements about the course and assignments.

COURSE CONTENTS:

1. Introduction
   • Algorithmic Background
   • Data Structures
   • Geometric Preliminaries
   • Models of Computation
2. Geometric Searching
   • Introduction
   • Point-Location Problems
   • Range-Searching Problems
3. Convex Hulls
   • Preliminaries
   • Problem Statement and Lower Bounds
   • Convex Hull Algorithms in the Plane
   • Graham's Scan
   • Jarvis's March
   • QUICKHULL techniques
   • Dynamic Convex Hull
   • Convex Hull in 3D
4. Proximity Problem
   • A Collection of Problems
   • A Computational Prototype: Element Uniqueness
   • Lower Bounds
   • The Closest-Pair Problem: A Divide-and-Conquer Approach
   • The Voronoi Diagram
   • Proximity Problems Solved by the Voronoi Diagram
5. Triangulation
   • Planar Triangulations
     • Greedy Triangulations
     • Partitioning a Polygon into Monotone Pieces
     • Triangulating a Monotone Polygon
   • Delaunay Triangulation
6. Intersections
   • Application Areas
   • Planar Applications: Intersection of Convex Polygons, Star-shaped Polygons; Intersection of Line Segments.
   • 3D Applications: Intersection of 3D Convex Polyhedra; Intersection of Half-spaces

TEXTBOOK INFO

Main Textbooks:

1. Computational Geometry: An Introduction, F. P. Preparata and M.I. Shamos, Springer-Verlag, 1985. [Download]
2. Computational Geometry: Algorithms and Applications, M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Springer-Verlag, Revised Second Edition, 2000. [Download]

References:

1. Joseph O'Rourke, Computational Geometry in C, Cambridge University Press, 2nd Edition, 1998. [Download]

GRADING: (Tentative)

• Midterm 20 %
• Final 30 %
• Assignments 20 %
• Term Project 30 %

• About this document ...