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.
CMSC 451 (Algorithms), or its equivalent:
- Knowledge of basic algorithm design techniques, such as divide-and-conquer, 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).
- Computational Geometry: Algorithms and Applications (2nd Edition), M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Springer-Verlag, 2000.
Course grades will be based on homeworks (roughly 5 of them) and a midterm and comprehensive final exam. The final exam will be on Monday, May 14, 8-10am. (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.
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 publically 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.
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.
- Basic Euclidean geometry
- Grids and Hulls:
- Fixed-radius near neighbors, convex hull algorithms, dominance and applications.
- Linear Programming:
- Half-plane intersection and randomized LP, backwards analysis, applications of low-dimensional LP.
- Intersections and Triangulation:
- Plane-sweep line segment intersection, triangulation of monotone subdivisions, plane-sweep triangulation of simple polygons.
- Point Location:
- Kirkpatrick's method, trapezoidal decompositions and analysis, history DAGs.
- Voronoi Diagrams:
- Basic definitions and properties, Fortune's algorithm.
- Geometric Data Structures:
- kd-trees, 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 zone-theorem, applications.
- Geometric Approximation:
- Dudley's theorem and applications, well-separated pair decompositions and geometric spanners, VC dimension, epsilon-nets and epsilon-approximations,
- Geometric Retrieval:
- kd-trees, range trees, hereditary segment trees, nearest neighbor searching.