Introduction
This is an introductory course to 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.
General Information
|
Required Text
- Computational Geometry: Algorithms and Applications, (2nd Edition), M. deBerg, M. vanKreveld, M. Overmars, O. Schwarzkopf, Springer-Verlag, 2000.
Course Structure
This semester, CMSC 754 and CMSC 741 (Geometric and Solid Modeling) will be taught in conjunction with each other. These two courses share a number of topics, and so some of the material in CMSC 754 will be taught by Prof. Leila DeFloriani (and I will teach some of the topics in 741).
Prof. DeFloriani has agreed to allow CMSC 754 students to visit her during her office hours to ask questions regarding the material that she will be covering. (For information on her office hours, please visit the class web page for CMSC 741.) I will be responsible for all other elements of CMSC 754, such as the administration and grading of homeworks and exams.
Prerequisites
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).
Course Work
Course grades will be based on homeworks (roughly 5 of them) and a midterm and comprehensive final exam. The midterm is tentatively scheduled for Thu, Oct 27. The final exam will be on Fri, Dec 16, from 8:00-10:00am. (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.
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 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.
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:
- Fixed-radius near neighbors, convex hull algorithms, dominance and applications.
- Shape:
- Basics of topology, complexes, manifolds and pseudo-manifolds.
- 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 Shape Representations:
- Topological relations in cell and simplicial complexes, edge-based data structures for cell complexes, data structures for general complexes.
- 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,
- Shape Simplification:
- Mesh and curve simplification, level of detail.
- Geometric Retrieval:
- kd-trees, range trees, hereditary segment trees, nearest neighbor searching.