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