CMSC 754
Spring 2020
Dave Mount

Syllabus

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.

Prerequisites

Minimum grade of C- in CMSC451 (Algorithms) and CMSC420 (Advanced Data Structures).

• 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 written homeworks (roughly 5 of them), a midterm exam, and a comprehensive final exam. (There will be no programming assignments.) Tentative weights: Homeworks: 25%, Midterm: 30%, Final: 45%.

Normally, late homeworks will not be accepted (because solutions will be discussed in class). If you feel that you have a legitimate excuse for handing in a homework late, contact me at least 48 hours before the due date. All homework assignments are to be done individually, but discussion with classmates regarding general solution strategies is allowed.

The Midterm Exam will be on Thu, Mar 12 in class. The Final Exam will be on Fri, May 15, 8:00-10:00am.

Topics

The following is very tentative, and the order of topics may be changed.

• Preliminaries: 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: 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,

Text and Resources

There is no required text. The books below are suggested reference material, particularly the first. Of course, there is a lot of information on the Web.

Excused Absences

Missing an exam for reasons such as illness, religious observance, participation in required university activities, or family or personal emergency (such as a serious automobile accident or close relative's funeral) will be excused so long as the absence is requested in writing at least 2 days in advance of the exam date and the student includes documentation that shows the absence qualifies as excused.

For medical absences, you must furnish documentation from the health care professional who treated you. This documentation must verify dates of treatment and indicate the time-frame that the student was unable to meet academic responsibilities. In addition, it must contain the name and phone number of the medical service provider to be used if verification is needed. No diagnostic information will ever be requested. Note that simply being seen by a health care professional does not constitute an excused absence; it must be clear that you were unable to perform your academic duties.

It is the University's policy to provide accommodations for students with religious observances conflicting with exams, but it is the your responsibility to inform the instructor in advance of intended religious observances. If you have a conflict with one of the planned exams, you must inform the instructor prior to the end of the first two weeks of the class.

Besides the policies in this syllabus, the University's policies apply during the semester. Various policies that may be relevant appear in the Undergraduate Catalog.

Students with Disabilities

Students with disabilities who have been certified by University's Accessibility & Disability Service as needing any type of special accommodations should see the instructor as soon as possible during the schedule adjustment period (the first two weeks of class). Please provide ADS's letter of accommodation to the instructor at that time.

All arrangements for exam accommodations as a result of disability must be made and arranged with the instructor at least 3 days prior to the exam date.