Ham Sandwich Two-Color Point Cut
One straight cut can balance two colors at once, while points on the cutting line explain the degenerate cases.
Free theory articleOne straight cut can balance two colors at once, while points on the cutting line explain the degenerate cases.
Concept & interpretation
The Ham Sandwich theorem states that any two sets of points in the plane can be simultaneously bisected by a single straight line. For discrete point sets with an odd number of points, we seek a weak bisection where the line passes through at least one point of each color, and each open half-plane contains at most half of the remaining points of each color.
experiment
In the interactive module, you can explore the existence and uniqueness of the ham-sandwich cut across different point configurations and shear transformations.
- Select the "Separated" point configuration to see standard non-overlapping sets.
- Change the configuration to "Interlaced" or "Collinear" to observe how the cut adapts, even going through multiple points.
- Apply a horizontal shear to verify that affine transformations preserve the relative half-plane properties.
- Adjust the "Cut rank" to cycle through multiple valid cuts if they exist.