Joint Mathematics Meetings

(For updated locations, see the timetable; All locations are subject to change)
Pdf version here

MAA Short Course

Discrete and Computational Geometry
Satyan L. Devadoss, Williams College, and Joseph O'Rourke, Smith College

This two-day MAA Short Course will take place on Monday and Tuesday, January 2 and 3, in Back Bay Ballroom C, 2nd Floor, Sheraton, before the annual meeting begins.

Registration

Advance registration fees are: member of the AMS or MAA, US$153; nonmembers are US$204; students, unemployed, or emeritus are US$77. These fees are in effect until December 13. If you choose to register at the meeting, the fees are US$163 for members of the AMS or MAA, US$214 for nonmembers, and US$87 for students, unemployed, or emeritus.

Advance registration will begin on September 1, 2011. Onsite registration will take place on Monday, January 2, 2012, 8:00 a.m. - noon, Back Bay Ballroom D, Sheraton.

Overview

Although geometry is as old as mathematics itself, discrete geometry only fully emerged in the 20th century, and computational geometry was only christened in the late 1970s. The terms “discrete” and “computational” fit well together as the geometry must be discretized in preparation for computations. “Discrete” here means concentration on finite sets of points, lines, triangles, and other geometric objects, and is used to contrast with “continuous” geometry, for example, smooth manifolds. Although the two endeavors were growing naturally on their own, it has been the interaction between discrete and computational geometry that has generated the most excitement, with each advance in one field spurring an advance in the other.  The interaction also draws upon two traditions: theoretical pursuits in pure mathematics and applications-driven directions often arising in computer science. The confluence has made the topic an ideal bridge between mathematics and computer science.  It is precisely to bridge that gap that we hope to accomplish with this short course.

The material that covered is accessible to faculty and scholars at several different levels, whether they are interested in teaching or research: whether teaching students at an advanced high school level, a collegiate setting, or at the graduate level, and research specifically on the topics covered or in allied fields. The reason this course allows for such breadth is due to the subject material.  A solid understanding of proofs is all that is needed to tackle some of the most beautiful and intriguing questions in this field.  Moreover, a strong intuition of this subject can be obtained and developed through visualization.  Due to the relative youth of the field, there are many accessible unsolved problems, which we highlight throughout the course. Although some have resisted the assaults of many talented researchers and might be awaiting a theoretical breakthrough, others may be accessible with current techniques and only await significant attention by an enterprising researcher. The field has expanded greatly since its origins and now the new connections to areas of mathematics and new application areas seems only to be accelerating. We hope this course can serve to open the door on this rich and fascinating subject.

Topics Covered

Our short course is broken into eight lectures, all given by the two organizers.

Introductory Session:  This lecture is meant to introduce the worlds of the “discrete” and the “computational” to a mathematical audience.  The key tool will be the study of polygons and polyhedra, the building blocks of 2D and 3D discrete geometry.  Topics will include triangulations, enumerations, and dissections, culminating in Max Dehn's counterexample to David Hilbert's third problem.

  1. Why “Computational” Geometry?
  2. Polygonal Building Blocks
  3. Scissors Congruence & Hilbert's third problem

Convex Hulls:  Although a convex hull of a set of points in the plane is easy enough to define, how does one go about computing it?  What does it mean to construct a geometric algorithm, and how can one measure better algorithms?  We look at several powerful algorithms for 2D hulls, and glimpse into the difficulties with 3D hulls.

  1. Incremental Algorithm
  2. Analysis of Algorithms
  3.  Graham Scan Algorithm

Triangulations: This lecture focuses on the partitioning a set of points in the plane into triangles, forming the basis for numerous real-world applications such as terrain meshing and face recognition.  We start with basic algorithms and combinatorics and then consider the discrete space of all triangulations (the flip graph). We then concentrate on what is arguably the most important triangulation, the Delaunay triangulation, having striking properties and playing a central role in many applications.

  1. Basic Combinatorics
  2. The Flip Graph
  3. Delaunay Triangulation

Voronoi Diagrams: Our interest is now on which point of a point set is closest to an arbitrary point in the plane. This focus on “nearest neighbors” leads to the rich geometry of the Voronoi diagram. Moreover, there is an intimate connection via duality between Voronoi diagrams and the Delaunay triangulations from above. And there is a beautiful and deep connection between both these structures and convex hulls in 3D.

  1. Voronoi Geometry
  2. Duality
  3. Convex Hull Revisited

Curves:  We extend the Voronoi diagram to apply to curves rather than to just sites, leading to two generalizations: the medial axis (useful in biology) and the straight skeleton (useful in orgiami).   This will bring us to curve shortening, which connects to several deep theorems of mathematics, most notably the Poincaré conjecture using the heat equation.  We close with curve reconstruction, an important practical task whose algorithms employ Voronoi diagrams, Delaunay triangulations, and the medial axis.

  1. Medial Axis, Straight Skeleton and Origami
  2. Curve Shortening and the Poincaré Conjecture
  3. Curve Reconstruction

Polyhedra:   Although we encounter polyhedra in earlier lectures, we study them more systematically with the dual goal of strengthening 3D intuition and presenting several theorem gems.   Considering shortest paths on convex polyhedra, a topic which brings us back to the ubiquitous Voronoi diagram, presents one of the most beautiful open problems on edge-unfolding polyhedra.  We follow that with two beautiful and useful theorems: The Gauss-Bonnet Theorem and Cauchy's Rigidity Theorem.

  1. Unfolding
  2. Gauss-Bonnet Theorem
  3. Cauchy's Rigidity Theorem

Configuration Spaces: This lecture explores configuration spaces for the simplest articulated objects, the open polygonal chains, which brings us to several famous problems on locked chains.   This in turn leads to an investigation of closed polygonal chains, concentrating on the topology of the space of polygons.   We close with an advanced topic, the structure of the configuration space of moving and colliding particles, leading back to the intricate combinatorics of the triangulations of convex polygons.

  1. Polygonal Chains
  2. Locked Chains
  3. Particle Collisions

Concluding Session:  Knowing all of this information, how does one excite and influence the next generation of scholars and teachers?  We share with the audience our success and failures as teachers in the classroom, and our approaches to undergraduate research in this area.  We close with current trends of this amazing subject, as it moves into the fields of biology, statistics, and beyond.

  1. Pedagogy
  2. Undergraduate Research
  3. Current Trends

Top of page