The famous Ham-Sandwich theorem states that any d point sets in ℝ^d can be simultaneously bisected by a single hyperplane. The α-Ham-Sandwich theorem gives a sufficient condition for the existence of biased cuts, i.e., hyperplanes that do not cut off half but some prescribed fraction of each point set. We give two new proofs for this theorem. The first proof is completely combinatorial and highlights a strong connection between the α-Ham-Sandwich theorem and Unique Sink Orientations of grids. The second proof uses point-hyperplane duality and the Poincaré-Miranda theorem and allows us to generalize the result to and beyond oriented matroids. For this we introduce a new concept of rainbow arrangements, generalizing colored pseudo-hyperplane arrangements. Along the way, we also show that the realizability problem for rainbow arrangements is ∃ℝ-complete, which also implies that the realizability problem for grid Unique Sink Orientations is ∃ℝ-complete.

Abstract It is well-known that the 2-Thief-Necklace-Splitting problem reduces to the discrete Ham Sandwich problem. In fact, this reduction was crucial in the proof of the $$\textsf{PPA}$$ -completeness of the Ham Sandwich problem [Filos-Ratsikas and Goldberg, STOC’19]. Recently, a variant of the Ham Sandwich problem called $$\alpha $$ -Ham Sandwich has been studied, in which the point sets are guaranteed to be well-separated [Steiger and Zhao, DCG’10]. The complexity of this search problem remains unknown, but it is known to lie in the complexity class $$\textsf{UEOPL}$$ [Chiu, Choudhary and Mulzer, ICALP’20]. We define the analogue of this well-separation condition in the necklace splitting problem — a necklace is n - separable , if every subset A of the n types of jewels can be separated from the types $$[n]\setminus A$$ by at most n separator points. Since this version of necklace splitting reduces to $$\alpha $$ -Ham Sandwich in a solution-preserving way it follows that instances of this version always have unique solutions. We furthermore provide two FPT algorithms: The first FPT algorithm solves 2-Thief-Necklace-Splitting on $$(n-1+\ell )$$ -separable necklaces with n types of jewels and m total jewels in time $$2^{O(\ell \log \ell )}+O(m^2)$$ . In particular, this shows that 2-Thief-Necklace-Splitting is polynomial-time solvable on n -separable necklaces. Thus, attempts to show hardness of $$\alpha $$ -Ham Sandwich through reduction from the 2-Thief-Necklace-Splitting problem cannot work. The second FPT algorithm tests $$(n-1+\ell )$$ -separability of a given necklace with n types of jewels in time $$2^{O(\ell ^2)}\cdot n^4$$ . In particular, n -separability can thus be tested in polynomial time, even though testing well-separation of point sets is $$\textsf{coNP}$$ -complete [Bergold et al., SWAT’22].

We provide polynomial-time reductions between three search problems from three distinct areas: the P-matrix linear complementarity problem (P-LCP), finding the sink of a unique sink orientation (USO), and a variant of the $α$-Ham Sandwich problem. For all three settings, we show that "two choices are enough", meaning that the general non-binary version of the problem can be reduced in polynomial time to the binary version. This specifically means that generalized P-LCPs are equivalent to P-LCPs, and grid USOs are equivalent to cube USOs. These results are obtained by showing that both the P-LCP and our $α$-Ham Sandwich variant are equivalent to a new problem we introduce, P-Lin-Bellman. This problem can be seen as a new tool for formulating problems as P-LCPs.

It is well-known that the 2-Thief-Necklace-Splitting problem reduces to the discrete Ham Sandwich problem. In fact, this reduction was crucial in the proof of the PPA-completeness of the Ham Sandwich problem [Filos-Ratsikas and Goldberg, STOC'19]. Recently, a variant of the Ham Sandwich problem called $α$-Ham Sandwich has been studied, in which the point sets are guaranteed to be well-separated [Steiger and Zhao, DCG'10]. The complexity of this search problem remains unknown, but it is known to lie in the complexity class UEOPL [Chiu, Choudhary and Mulzer, ICALP'20]. We define the analogue of this well-separability condition in the necklace splitting problem -- a necklace is $n$-separable, if every subset $A$ of the $n$ types of jewels can be separated from the types $[n]\setminus A$ by at most $n$ separator points. By the reduction to the Ham Sandwich problem it follows that this version of necklace splitting has a unique solution. We furthermore provide two FPT algorithms: The first FPT algorithm solves 2-Thief-Necklace-Splitting on $(n-1+\ell)$-separable necklaces with $n$ types of jewels and $m$ total jewels in time $2^{O(\ell\log\ell)}+m^2$. In particular, this shows that 2-Thief-Necklace-Splitting is polynomial-time solvable on $n$-separable necklaces. Thus, attempts to show hardness of $α$-Ham Sandwich through reduction from the 2-Thief-Necklace-Splitting problem cannot work. The second FPT algorithm tests $(n-1+\ell)$-separability of a given necklace with $n$ types of jewels in time $2^{O(\ell^2)}\cdot n^4$. In particular, $n$-separability can thus be tested in polynomial time, even though testing well-separation of point sets is coNP-complete [Bergold et al., SWAT'22].