Ham-Sandwich cuts and center transversals in subspaces

Abstract

The Ham-Sandwich theorem is a well-known result in geometry. It states that any $d$ mass distributions in ${\mathbb{R}}^d$ can be simultaneously bisected by a hyperplane. The result is tight, that is, there are examples of $d+1$ mass distributions that cannot be simultaneously bisected by a single hyperplane. In this abstract we will study the following question: given a continuous assignment of mass distributions to certain subsets of ${\mathbb{R}}^d$, is there a subset on which we can bisect more masses than what is guaranteed by the Ham-Sandwich theorem? We investigate two types of subsets. The first type are linear subspaces of ${\mathbb{R}}^d$, i.e., $k$-dimensional flats containing the origin. We show that for any continuous assignment of $d$ mass distributions to the $k$-dimensional linear subspaces of ${\mathbb{R}}^d$, there is always a subspace on which we can simultaneously bisect the images of all $d$ assignments. We extend this result to center transversals, a generalization of Ham-Sandwich cuts. As for Ham-Sandwich cuts, we further show that for $d-k+2$ masses, we can choose $k-1$ of the vectors defining the $k$-dimensional subspace in which the solution lies. The second type of subsets we consider are subsets that are determined by families of $n$ hyperplanes in ${\mathbb{R}}^d$. Also in this case, we find a Ham-Sandwich-type result. In an attempt to solve a conjecture by Langerman about bisections with several cuts, we show that our underlying topological result can be used to prove this conjecture in a relaxed setting.

In proceedings of the 35th International Symposium on Computational Geometry (SoCG 2019)