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.
By Riano · Published · Updated · Report a correction
Ham Sandwich Two-Color Point Cut
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.
worked-example
Consider a configuration where red points are at (-3, -1), (-2, 2), (-1, 0) and blue points are at (1, 0), (2, -2), (3, 1). We test lines connecting one red point and one blue point. For example, connecting red point (-1, 0) and blue point (1, 0):
| Points | Equation | Normalized Coefficients (a, b, c) |
|---|---|---|
| (-1, 0) and (1, 0) | (0 - 0)x + (1 - (-1))y + ((-1)(0) - (1)(0)) = 0 | (0, 2, 0) → (0, 1, 0) |
This line is the x-axis (y = 0). Checking the remaining points: Red point (-3, -1) has y < 0 (negative), (-2, 2) has y > 0 (positive). Blue point (2, -2) has y < 0 (negative), (3, 1) has y > 0 (positive). Since each open half-plane has exactly 1 red and 1 blue point, it is a valid ham-sandwich cut.
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.
limitations
The interactive module uses a brute-force exhaustive enumeration of all pairs of red and blue points. This is suitable for demonstrating the concept on small sets but is not an optimal algorithm for large n.
- The algorithm checks all possible O(n²) connecting lines.
- For large datasets, advanced techniques like the Cole-Sharir-Yap algorithm would be necessary, running in O(n log n) time.
references
Primary references detailing the ham-sandwich theorem, discrete bisections, and efficient computational geometry algorithms:
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Ham Sandwich Two-Color Point Cut module.
Try Ham Sandwich Two-Color Point Cut on Riano →