Course Objectives
This is an introductory course on computational geometry and its applications. We will discuss techniques needed in designing and analyzing efficient algorithms and data structures for computational problems in discrete geometry, such as convex hulls, geometric intersections, geometric structures such as Voronoi diagrams and Delaunay triangulations, arrangements of lines and hyperplanes, and range searching.
Text
Recommended References
 Foundations of Multidimensional and Metric Data Structures, H. Samet, MorganKaufman, 2006.
 Geometric Approximation Algorithms, S. HarPeled, American Mathematical Society, 2010.
 Lectures on Discrete Geometry, J. Matousek, Springer, 2002.
Prerequisites
CMSC 451 (Algorithms), or its equivalent:
 Knowledge of basic algorithm design techniques, such as divideandconquer, greedy algorithms, dynamic programming.
 Knowledge of basic analysis techniques such as asymptotic notation, solving summations and recurrences, basic probability theory.
 Knowledge of basic data structures (e.g. balanced binary trees, heaps, and hashing).
Course Work
Course grades will be based on homeworks (roughly 5 of them) and a midterm and comprehensive final exam. (There will be no programming projects.) Tentative weights: Homeworks: 25%, Midterm: 30%, Final: 45%.
Normally, late homeworks will not be accepted. If you think that you have a legitimate excuse for handing in a homework late, contact me before the due date.
The date of the Midterm Exam will be announced later. The Final Exam will be on Saturday, December 17, 10:30am12:30pm.
Academic Dishonesty
All class work is to be done independently. It is best to try to solve problems on your own, since problem solving is an important component of the course, and exam problems are often based on modifications of homework problems. You are allowed to discuss class material, homework problems, and general solution strategies with your classmates. But, when it comes to formulating or writing solutions you must work alone. You may use free and publicly available sources, such as books, journal and conference publications, and web pages, as research material for your answers. (You will not lose points for using external sources.)
You may not use any service that involves payment, and you must clearly and explicitly cite all outside sources and materials that you made use of. I consider the use of uncited external sources as portraying someone else's work as your own, and as such it is a violation of the University's policies on academic dishonesty. Instances will be dealt with harshly and typically result in a failing course grade.
Unless otherwise specified, you should assume that that the UMD Code of Academic Integrity applies.
Topics
The following list of topics is very tentative. Depending on time, some topics may be added or dropped, and the order of topics may change.
 Preliminaries:
 Basic Euclidean geometry
 Grids and Hulls:
 Fixedradius near neighbors, convex hull algorithms, dominance and applications.
 Linear Programming:
 Halfplane intersection and randomized LP, backwards analysis, applications of lowdimensional LP.
 Intersections and Triangulation:
 Planesweep line segment intersection, triangulation of monotone subdivisions, planesweep triangulation of simple polygons.
 Point Location:
 Trapezoidal decompositions and analysis, history DAGs.
 Voronoi Diagrams:
 Basic definitions and properties, Fortune's algorithm.
 Geometric Data Structures:
 kdtrees, range trees and range searching, segment trees.
 Delaunay Triangulations:
 Point set triangulations, basic definition and properties, randomize incremental algorithm and analysis.
 Arrangements and Duality:
 Point/line duality, incremental construction of arrangements and the zonetheorem, applications.
 Geometric Approximation:
 Dudley's theorem and applications, wellseparated pair decompositions and geometric spanners, VC dimension, epsilonnets and epsilonapproximations,
 Geometric Retrieval:
 kdtrees, range trees, hereditary segment trees, nearest neighbor searching.
