Visualization: The Ham Sandwich Cut

The Ham Sandwich Theorem states that, for n objects in Euclidian space, it is possible to divide all of them in half with a single (n - 1) dimensional hyperplane. This site is a visualization of how we compute the cut in two dimensions. In computational geometry, the problem can be stated as: given sets of red and blue points, compute a line that divides both the red points in half and the blue points in half.

The Ham Sandwich Cut

An important concept for this problem is Duality. Duality is a method for representing a problem in an analogous plane, and can help with solving seemingly complicated problems because if we find a solution in the dual plane, we have also found a solution in the primal plane.

In our dual plane we convert points to lines and lines to points. The exact conversion is as follows: each point (a,b) translates to a line of the form
y = (a/100)x + b. (We divide a to get reasonable slopes on our graph.)

The line you see is the dual line for the point under the cursor. Since we are only dealing with points in the primal plane, we only have lines in the dual plane.

Click to add red points.

For simplicity's sake please add an even number of points.

0 | 0