CS 564 COMPUTATIONAL GEOMETRY (Spring 2012)

Instructor: Ugur Güdükbay (Room 403, Tel: 1486)
Office Hours: Tuesday 8:40-10:30
Course Schedule: Tuesday 13:40, 14:40 (EB203), Thursday 15:40, 16:40 (EB203)
Course Assistant: None.
Course Homepage.
Please visit the course homepage frequently to see the announcements about the course and assignments.

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.
2. Computational Geometry: Algorithms and Applications, M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Springer-Verlag, Revised Second Edition, 2000. (The bookstore will order this book.)

GRADING: (Tentative)
Midterm I 20 %, Final 30 %
A Project 35 %, Assignments 10 %, Attendance 05 %

• About this document ...