Introduction: typical problems, applications and shortcomings. [1 hr]
Fixed-Radius Nearest Neighbors and Geometric Basics - introduction to affine geometry. [2 hr]
Convex hulls: introduction, Grahams scan algorithm, Divide and conquer algorithm,
Quick hull, Jarvis March, Chan's algorithm. [3 hr]
Line segment intersection: Parametric representation, Plane sweep algorithm. [3 hr]
Planar Graphs, Polygons and Art Galleries. [3 hr]
Polygon Triangulation. [3 hr]
Half-plane Intersection problem, point-line duality. [3 hr]
Linear Programming: LP in higher dimensional spaces, Deterministic incremental construction,
Randomized construction, Smallest enclosing disk problem. [3 hr]
Orthogonal Range Searching and Kd trees. Segment trees and red blue intersections. [3 hr]
Planar point location and trapezoidal maps. [3 hr]
Voronoi's diagram: Fortunes algorithm. [3 hr]
Delaunay Triangulations. [3 hr]
Line arrangements: Application of arrangements. [3 hr]
Shortest Paths and Visibility Graphs. [3 hr]

To learn the basic concepts of convex hulls.

To learn point location, range queries, Voronoi diagram and Delunay triangulations.

To learn half-plane intersection, application to linear programming.

To learn the different Geometric searching and Sweep techniques.

After carrying out the course, students will:
1. understand the concepts of convex hulls and its applications in real world problems
2. comprehend the notions of linear programming through the application of half-plane intersections
3. master the concepts of point location in planar maps
4. have a better understanding of range queries, Voronoi diaghrams and Delunay triangulations.

Mark de Berg, Otfried Schwarzkopf, Marc van Kreveld and Mark Overmars, Computational Geometry: Algorithms and Applications, Springer

Joseph O' Rourke, Computational Geometry in C, Cambridge University Press

David Mount, Lecture notes, NA , http://www.cs.umd.edu/~mount/754/Lects/754lects.pdf

F. P. Preparata and Michael I. Shamos, Computational Geometry: An Introduction, Springer

Surveys on Discrete and Computational Geometry: Twenty Years Later. Jacob E. Goodman, János Pach and Richard Pollack, Editors. Contemporary Mathematics. 2008. http://dx.doi.org/10.1090/conm/453