This is a reading and assignment course covering a range of topics related to geometric representation and computation. We will study fundamental data structures and algorithms from computational geometry and computer graphics, their application to problems that occur in practice, and (as part of an optional programming component) techniques for visual inspection of and interaction with geometric entities and running geometric algorithms.

Current Handouts:  Course Information;    Syllabus; Signup Sheet

Presentation Schedule is posted here.

Presentations (in chronological order):
(Nota bene: If you are interested in printing these documents using fewer pieces of paper, please see the directions from Athena Consulting on Printing MULTIPLE PAGES on one page.)

      Lecture 1 (2D Chull) (as ps)

      Lecture 2 (Segment Intersection) (as ps)

      Lecture 3 (LP in Low Dimension)

      Lecture 4 (Polygon Triangulation)

      Lecture 5 (Range Searching) (as ps)

      Lecture 6 (2D Point Location)

      Lecture 7 (2D Voronoi Diagrams) (as pdf)

      Lecture 14 (2D BSP) (as pdf)

      Lecture 9 (2D Arrangements) (as pdf)      Duality Demo (Applet)

      Lecture 10 (2D Delaunay Triangulation) (as pdf)

      Lecture 11 (Adjacency Data Structures) (as ps)

      Lecture 8 (Robustness, Chee Yap) See also Exact Geometric Computation at NYU

      Lecture 13 (Smooth Surfaces)

      Lecture 12 (3D Convex Hull)

      Lecture 14 (2D BSP) (as pdf)

      Lecture 15 (Kinetic Algorithms)

      Lecture 16 (Motion Planning)

      Lecture 17 (Quadtrees)

      Lecture 18 (Visibility)

      Lecture 19 (Visibility)

      Lecture 20 (LP in High Dimension)

      Lecture 21 (Closest Pair)

      Lecture 22 (Approximate Nearest Neighbor)

      Lecture 23a (Iterative Algorithms: ICP)

      Lecture 23b (Iterative Algorithms: Mesh Simplification)

      Lecture 24 (Approximate Nearest Neighbor -- Hamming)

      Lecture 25 (Low-Distortion Embeddings)

      Lecture 26 (Reductions to Approximate NN)

Problem Sets:

     Problem Set 1 (as ps)  PS1 Solutions (as ps)

        Exemplary solutions to PS1:    Daniel Vlasic's     Jason Yang's

     Problem Set 2 (as ps)

        Exemplary solutions to PS2:     Matt Seegmiller's    Daniel Vlasic's    Jason Yang's

     Problem Set 3 (as ps)

Topics include: 2D Convex Hulls, Segment Intersection and Map Overlay,
Low-Dimensional Linear Programming, and Polygon Triangulation.

Also: Orthogonal Range Searching, Point Location and Spatial Indexing,
Voronoi Diagrams, Robustness and Perturbation Schemes, Arrangements
and Duality, Delaunay Triangulations.

Also: Representing Polyhedra, Convex Hulls, Smooth Surfaces, Binary
Space Partitions, Kinetic Algorithms, Robot Motion Planning, Quad-
trees and Non-Uniform Meshing.

Also: Visibility Data Structures, Medial Axis and Surface Reconstruction,
Higher- and High-Dimensional Linear Programming, Closest Pair, Approx-
imate Nearest Neighbor, Iterative Algorithms, Low-Distortion Embeddings,
and Reductions to Approximate Nearest Neighbor.

Readings will come from the textbook, de Berg et al.'s Computational
Geometry:  Algorithms and Applications, and from selected classic
and modern papers from the research literature.  Each topic will
be co-presented by students and instructors, with significant effort
devoted ahead of time to the student's command of the material.

There will be four assignments, roughly one every three
weeks.  Each assignment will have a required theoretical component,
and optional theoretical and programming components.  There will
be no exams, final or final projects.

Enrollment is by permission of the instructors, and may be limited.
Please complete a signup sheet at the first class meeting.
 

Format

A typical class meeting will consist of an instructor or student presentation of papers and software, and a discussion of the material co-led by the student and instructor. Each lecture, one student will be expected (given several weeks' notice) to summarize the material for that lecture and help lead a discussion of the readings.  Two weeks before the student is to present, s/he will meet with the instructors to plan the presentation.  One week before the student is to present, s/he will be expected to submit a "pre-talk" (a draft version of the overheads to be used) and an initial treatment of the "talking points" suggested by the instructors, as well as any other discussion topics the student wishes to cover in class.

The teaching staff will provide timely feedback about the presentation.

All class members will be expected to have read the listed readings by the start of the relevant class.
 

Assignments

There will be four required problem sets (worked problems with paper and pencil).

Each assignment will have an optional programming component.  These are intended to get implementation-minded students familiar with crafting technically substantive and visually interesting geometric applications.

For those who do not wish to do any programming, each assignment has an optional component of additional worked problems.
 

Grades

Course grades will be based on the presentation development, on the presentation itself, and on the assignments.

Last modified: Aug 2001