CS 478 COMPUTATIONAL GEOMETRY (Spring'2000-2001)

Instructor: Ugur Güdükbay (Room 524, Tel: 1486)
Office Hours: Monday 8:40-10:30 Friday 8:40-9:30
Course Schedule: Wednesday 15:40-16:30 (EB162), Friday 14:40-16:30 (EB261)
Course Assistant: Ediz Saykol (Room 526, Tel: 1776)
Assistant's Office Hours: Wednesday 14:40-15:30
Course Homepage: http://www.cs.bilkent.edu.tr/~gudukbay/cs478/index.html.
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 Textbook:

1. Computational Geometry: An Introduction, F. P. Preparata and M.I. Shamos, Springer-Verlag, 1985.

References:

1. Computational Geometry: Algorithms and Applications, M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Springer-Verlag, 1997.

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

• About this document ...