Lecture 1: Course Sneak Preview, Equidecomposing Polygons

Overview
Finite 2D Polygon Equidecomposability (Details)
Equidecomposability Code/Demo
Further Reading / Studying

Overview

Today's lecture was mostly spent on course policies and an overview of all assignments. But I gave a brief lecture on the math for one of the possible final projects on "Equidecomposability." We showed a constructive proof that for two polygons A and B with the same area, it is possible to cut A into a finite number of pieces that can be rigidly re-arranged like a puzzle to form polygon B. This is known as the Wallace Bolyai Gerwein theorem. For details, read on to the next section. I am hoping that at least one group will use this concept to cut two surfaces represented as triangles meshes into each other for the final project.

Students also took a 10 minute ungraded, anonymous knowledge assessment

Finite 2D Polygon Equidecomposability

In order to cut one polygon into another, we first need two intermediate steps

Triangle To A "Canonical Rectangle"

First, for any triangle, we need to figure out some way to cut it into some rectangle with the same area. Given the scheme below, I will call such a rectangle a "canonical rectangle." This is done by choosing some vertex on the triangle ABC, say vertex A, and dropping a perpendicular to the opposite side BC. This will be the first cut. Then, make another cut perpendicular to the first cut which is halfway through it (half the height of the triangle h). This partitions the triangle into two triangles and a trapezoid. In the image below, they are triangles ADE, AEF, and trapezoid DBCF. Now note that in the image below, triangle AEF is congruent to triangle CHF the opposite angles and the fact that they are both right triangles, plus AE and CH are both length h/2. By the same argument, triangle ADE is congruent to triangle BDG. We can rotate both of these triangles around points F and D to form a rectangle, as shown below

Note that some care has to be taken if ABC is an obtuse triangle (a triangle with one angle greater than 90 degrees). In this case, depending on the choice of vertex A, it is possible that dropping a perpendicular will leave the triangle:

In this case, simply relabel the triangle so that the perpendicular is dropped starting at the vertex corresponding to the obtuse angle instead, and we're back in business:

Also, even in the case of an acute triangle, it is often wise to label the point A so that the pieces will be as even as possible, to prevent skinny pieces in the animation.

Rectangle To Rectangle: "Escalator Method"

We also need a way to cut any rectangle into any other rectangle with the same area. To do this, take two such rectangles and align them at their lower left corner so that the taller rectangle is labeled ABCD and the wider rectangle is labeled EBFG, as in the picture below. Then, draw a line segment from point A to point F, and label its intersection points with the polygons as J and K as shown below. Now note that triangle AKD is congruent to triangle JFG and triangle AEJ is congruent to triangle KCF. This is a little bit trickier to show than before. The proof involves showing that one of these pairs of triangles is similar, and then it uses the fact that rectangle ABCD and rectangle EBFB have the same area. If you don't use the fact that those two rectangles have the same area, the proof will fail (and in general when you're doing proofs and noticed you haven't used all of the information, you either proved something more general, or you made a mistake). Click here to see a detailed proof that my friend Alex Hallden-Abberton wrote out. 10 points extra credit to anyone who figures out a simpler proof.

Given that triangle AKD is congruent to triangle JFG, slide triangle AKD down line segment AF (the "escalator") until it coincides with triangle JFG. Do the same to slide triangle AEJ in to place over triangle KCF. The image below shows the final equivalences

Some care needs to be taken if the wider rectangle is more than two times wider than the taller rectangle. In this case, the escalator line is not contained within both polygons and the congruences are broken:

In this case, simply cut the wider rectangle in half and turn it into a rectangle with half the width and twice the height, until its width is less than twice the width of the taller rectangle:

Any Polygon To Any Polygon with The Same Area

Now that we can cut any triangle into some rectangle and any rectangle into other rectangle with the same area, we can combine the two steps to cut any triangle into any rectangle. This turns out to be enough to cut any polygon into any polygon. Reasoning through this was the big question of the day. It boils down to the following three observations

It is possible to to cut any polygon into a bunch of triangles. There is a very simple O(N^3) algorithm to do this for a simple polygon (no holes or self-intersections) that involves "ear cutting" (cutting off one triangle at a time and checking to make sure each triangle can be cut) and another not too much more complicated sweep line algorithm to do it in O(NlogN) time, but it is theoretically possible to do it in linear time, as shown by Bernard Chazelle. The problem has an O(N logN) lower bound for polygons with holes, which can be shown with a reduction to sorting. Anyway, for the purposes of this discussion, all we really need to know is that it's possible.
Once a polygon is cut up into a bunch of triangles, we can cut it into a square of the same area by using the steps we developed before to cut any triangle into any rectangle. In particular, let the area of the polygon be X². Then we cut each triangle into a rectangle with width X and stack all of those rectangles up on top of each other. See the example below for a polygon with six sides which has been cut into 4 triangles, each of which is cut into rectangles that are stacked up into a square:
For two polygons with the same area, each can be cut into the same square, and from there the pieces can be intersected to make smaller pieces that can be arranged to form one or the other shape. Now we have finally accomplished our objective of finding pieces that can be re-arranged into either polygon. This gets a bit messy, so below I'm only showing an example with two different triangles with the same area (the simplest case). In the picture below, the pieces from the triangle on the left are drawn with a blue border, and pieces from the triangle on the right are drawn with a black border. We'll talk about an algorithm towards the end of the first unit that can intersect two polygons and which is a key step in 3D rendering.

For those who chose to work on this for their final project, this is by far the trickiest step due to numerical precision difficulties intersecting polygons (you'll notice that some of the polygons are quite small) and the fact that by the nature of this algorithm, you will end up with many collinear vertices, while most algorithms assume points are in general position.

Equidecomposability Code/Demo

The code I ran today in class is in the github repository https://github.com/ctralie/Equidecomposability. To check it out, type


git clone --recursive git://github.com/ctralie/Equidecomposability.git

You will need to have the Python packages Numpy and Tkinter installed to run this. The entry point for cutting a triangle into a rectangle is tri2RectGUI.py. And the meat of the code that performs the cutting is in Equidecomposition.py. The code is a bit messy! I did this project in a very short amount of time when I myself was an undergraduate and have learned a lot since. I mainly hope this will serve as a reference for those groups who wish to work on Equidecomposability as their final project.

COMPSCI/MATH 290: Spring 2016