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.

We prove that an $\varepsilon$-approximate fixpoint of a map $f:[0,1]^{d} \rightarrow[0,1]^{d}$ can be found with $\mathcal{O}\left(d^{2}\left(\log \frac{1}{\varepsilon}+\log \frac{1}{1-\lambda}\right)\right)$ queries to f if f is $\lambda$-contracting with respect to an $\ell_{p}$-metric for some $p \in[1, \infty) \cup\{\infty\}$. This generalizes a recent result of Chen, Li, and Yannakakis [STOC 2024] from the $\ell_{\infty}$-case to all $\ell_{p}$ metrics. Previously, all query upper bounds for $p \in[1, \infty) \backslash\{2\}$ were either exponential in $d, \log \frac{1}{\varepsilon}$, or $\log \frac{1}{1-\lambda}$. Chen, Li, and Yannakakis also show how to ensure that all queries to f lie on a discrete grid of limited granularity in the $\ell_{\infty}$-case. We provide such a rounding for the $\ell_{1}$-case, placing an appropriately defined version of the $\ell_{1}$-case in FPdt. To prove our results, we introduce the notion of $\ell_{p}$-halfspaces and generalize the classical centerpoint theorem from discrete geometry: for any $p \in[1, \infty) \cup\{\infty\}$ and any mass distribution (or point set), we prove that there exists a centerpoint c such that every $\ell_{p}$-halfspace defined by c and a normal vector contains at least a $\frac{1}{d+1}$-fraction of the mass (or points).

The ARRIVAL problem is to decide the fate of a train moving along the edges of a directed graph, according to a simple (deterministic) pseudorandom walk. The problem is in NP∩coNP but not known to be in 𝖯. The currently best algorithms have runtime 2^Θ(n) where n is the number of vertices. This is not much better than just performing the pseudorandom walk. We develop a subexponential algorithm with runtime 2^O(√nlog n). We also give a polynomial-time algorithm if the graph is almost acyclic. Both results are derived from a new general approach to solve ARRIVAL instances.