I worked with another great undergrad this past spring as my DRP (directed reading program) student. This time, I was excited to talk about some geometry that I don't often think about: Discrete geometry. There are so many results that are surprising to me. For example, there are at most 30^n distinct triangulations for an arbitrary set of n points in the plane. That's the best universal bound that we have. That's wild! I find discrete geometry very interesting, and I was happy to find a student who did as well.
Here are some of the things we talked about that we had a lot of fun with during the semester:
Scissors congruence
We say that two planar objects are scissors congruent if you can cut one up into finite pieces and paste the pieces back together to form the other.
Fun facts:
No polygon is scissors congruent to a circle.
Any two polygons that have the same area are scissors congruent. (Wallace–Bolyai–Gerwien) This result uses the following three facts: - Any two rectangles with the same area are scissors congruent, - Any triangle and rectangle with the same area are scissors congruent, and - Any polygon can be triangulated. See if you can put the proof together, its a fun one! Epstein and Smirnov have something on github that will demonstrate the scissors congruence when you draw two polygons! (It resizes your polygons to have the same area.)
Another interesting thing that my student mentioned: scissors congruence reminded him of the connected sums, like when we glue two tori together to construct the surface of genus two. It also reminded him of when we cut and paste along identifications to look at something we already had in a new way, like below:
We talked it out; these operations care about identifications and preserving orientation (if what we have is orientable), and scissors congruence doesn't care about that at all. It is not a topological invariant, but it is an area invariant!
Triangulating collections of points
Talking about triangulating a finite collection of points in the plane required us to talk about convex hulls first. Given a set of points, S, the convex hull of S is the intersection of all convex regions that contain S. I often think of it as what you would get if you stretched a rubber band around S. There was some discussion about algorithms for finding convex hulls, as well as the various time complexities of each. One of our favorites was the Graham scan. Then, we went on to talk about triangulations.
A triangulation of a set of points is a set of maximal non-crossing edges between vertices. Any triangulation of a set of points will therefore contain its convex hull.
We came across something really fun, called the flip graph. The flip graph of S is the graph where the vertices are triangulations of S . Two triangulations are connected by an edge in the flip graph if an edge of one triangulation may be flipped to obtain the other. (For example, flipping the diagonal of a square.)
The flip graph of any point set in the plane is connected (Lawson, 1971). That means that for any set of points, you can get from one triangulation to any other by flipping edges! If you have some kind of ideal triangulation you'd like to get to and you start with a not so great triangulation, you can flip edges instead of starting all over again.
One type of triangulation we looked at was called the Delauney triangulation. I'm not really going to talk more about it here, but this triangulation can used for terrain reconstruction when each vertex also has an associated height. There's more on this in Discrete and Computational Geometry by S. Devadoss and J. O’Rourke.
We talked about some more things, including the art gallery problem, Voronoi diagrams and redistricting, how some of these ideas could work (or not work) in dimension 3, and how some of this fit into my student's wider knowledge of math.
Our references were
Discrete and Computational Geometry by S. Devadoss and J. O’Rourke (The flip graph above was basically one from this book)
A Graph Partitioning Model of Congressional Redistricting by S. Doyle in the Rose-Hulman Undergraduate Mathematics Journal
Applying Voronoi Diagrams to the Redistricting Problem by L. Svec et al. in UMAP.
We also looked at this site, which let's you play with a model for creating voting districts in Washington
A Political Redistricting Tool for the Rest of Us, by Evan Kleiner and Albert Schueller (There's more about the algorithm here, as well as the model you can try out near the end of the page)
If you're interested in what the other DRP students and mentors studied during Spring 2019 or other semester, take a look at the projects here.
Comments