Splitting Sandwiches Unevenly via Unique Sink Orientations and Rainbow Arrangements

As every subgrid has a sink by assumption, it remains to show that this sink is unique. Assume for the sake of contradiction that there is a subgrid that has two sinks $a=(a_1,\mathrm{\dots },a_d)$ and $b=(b_1,\mathrm{\dots },b_d)$. Consider now the subcube spanned by $a$ and $b$ (i.e., the subcube induced by $\{a_1,b_1\}\times \mathrm{\cdots }\times \{a_d,b_d\}$). As $a$ and $b$ were sinks in the subgrid, they are also sinks in this subcube. We have thus found a subcube with two sinks, so $\sigma$ restricted to this subcube is not a USO. This is a contradiction to the second assumption. $◀$

Let $𝒫=(P_1,\mathrm{\dots },P_d)\subset {ℝ}^d$ be a well-separated point set in weak general position. For $i\in [d]$, let $P_i=\{p_1^i,\mathrm{\dots },p_{|P_i|}^i\}$. Let ${\mathrm{\Gamma }}_{𝒫}$ be the grid graph parameterized by $|P_1|,\mathrm{\dots },|P_d|$. We recall the following orientation ${\sigma }_{𝒫}$ on ${\mathrm{\Gamma }}_{𝒫}$, which was presented in [10] and is illustrated in Figure 3. For any edge between two vertices $v=(a_1,\mathrm{\dots },a_{i-1},a_i,a_{i+1},\mathrm{\dots },a_d)$ and $v^{\prime }=(a_1,\mathrm{\dots },a_{i-1},a_i^{\prime },a_{i+1},\mathrm{\dots },a_d)$ of ${\mathrm{\Gamma }}_{𝒫}$, let $h$ be the colorful hyperplane spanned by the points $p_{a_1}^1,\mathrm{\dots },p_{a_{i-1}}^{i-1},p_{a_i}^i,p_{a_{i+1}}^{i+1},\mathrm{\dots },p_d^d$, and let $h^{\prime }$ be the colorful hyperplane spanned by $p_{a_1}^1,\mathrm{\dots },p_{a_{i-1}}^{i-1},p_{a_i^{\prime }}^i,p_{a_{i+1}}^{i+1},\mathrm{\dots },p_d^d$. If $p_{a_i^{\prime }}^i$ lies above $h$, we orient $v^{\prime }$ towards $v$; otherwise orient $v$ towards $v^{\prime }$. It turns out that $p_{a_i^{\prime }}^i$ lies above $h$ if and only if $p_{a_i}^i$ lies below the hyperplane $h^{\prime }$,⁴⁴4This can be seen by projecting to ${ℝ}^2$ such that $h\cap h^{\prime }$ is mapped to the origin. so this orientation is well-defined.

The following lemma is key to our first proof of Theorem 3.

Note that this lemma was already proved in [10]. However, their proof uses Theorem 3. To avoid the cyclic dependency, we provide here an alternative proof that uses the following version of the $\alpha$-Ham-Sandwich theorem for mass distributions.

We first show that every subgrid has a sink. By the definition of ${\sigma }_{𝒫}$, a subgrid is spanned by subsets $P_i^{\prime }\subseteq P_i$ and a sink corresponds to a $(1,\mathrm{\dots },1)$-cut. As any subset of a well-separated point set in weak general position is again well-separated and in weak general position, the existence of such a $(1,\mathrm{\dots },1)$-cut is guaranteed by applying Theorem 7 with the convex sets being the convex hulls of $P_1^{\prime },\mathrm{\dots },P_d^{\prime }$, and ${\alpha }_i=0$ for $i\in [d]$.

We now argue that every subcube is a USO. A subcube is spanned by at most two points per $P_i$. Let $Q_i$ be the set of these at most two points. As argued before, $(Q_1,\mathrm{\dots },Q_d)$ is well-separated and in weak general position. Further, the convex hull of the at most two points per $P_i$ is a line segment. Hence, by applying Theorem 7 on these convex hulls, we obtain the existence of all possible $({\alpha }_1,\mathrm{\dots },{\alpha }_d)$-cuts of $(Q_1,\mathrm{\dots },Q_d)$ for all $({\alpha }_1,\mathrm{\dots },{\alpha }_d)\in [|Q_1|]\times \mathrm{\cdots }\times [|Q_d|]$. Hence, in the subcube, each possible outmap (i.e., a binary vector at each vertex that encodes whether the incident edge along each dimension is incoming or outgoing) is present. This implies that the subcube is indeed a USO [31].

The claim now follows from Lemma 5. $◀$

The $\alpha$-Ham-Sandwich theorem for point sets (Theorem 3) now follows easily.

By Lemma 6, the orientation ${\sigma }_{𝒫}$ is a grid USO. We define a function $r:[|P_1|]\times \mathrm{\cdots }\times [|P_d|]\to \{0,\mathrm{\dots },|P_1|-1\}\times \mathrm{\cdots }\times \{0,\mathrm{\dots },|P_d|-1\}$ that assigns to each vertex of the grid graph ${\mathrm{\Gamma }}_{𝒫}$ a tuple $(a_1,\mathrm{\dots },a_d)$ such that $a_i$ is the number of the vertex’s outgoing edges in the dimension $i$. Then [15, Theorem 2.14] states that $r$ is a bijection. This implies that for every $({\alpha }_1,\mathrm{\dots },{\alpha }_d)\in [|P_1|]\times \mathrm{\cdots }\times [|P_d|]$, there is a unique $({\alpha }_1,\mathrm{\dots },{\alpha }_d)$-cut, as required. $◀$

By assumption $ℱ$ is $(\beta ,\gamma )$-separated, so for each vector $s\in {\{+,-\}}^d$ there is a point $x_s$ in an unbounded cell that lies above or below all relevant levels of a color class as stated in Definition 12. As the arrangement has finitely many cells, we can place a large enough ball $B$ that contains all the bounded cells. Observe that we can assume $x_s$ to lie outside of $B$. Consider a subset $I\subseteq [d]$ and a family of vectors $s^1,\mathrm{\dots },s^k$ for which $s_i^1=\mathrm{\dots }=s_i^k$ for all $i\in I$. Let ${ℱ}_{ℐ}$ be the union of all relevant levels, that is, the ${\alpha }_i$-levels for ${\alpha }_i\in \{{\beta }_i,\mathrm{\dots },{\gamma }_i\}$, of the color classes $i\in I$. We claim that the points $x_{s^1},\mathrm{\dots },x_{s^k}$ lie in a common unbounded cell of ${ℱ}_{ℐ}$. Indeed, assume for the sake of contradiction that two of the points $x_{s^i}$ and $x_{s^j}$ lie in different unbounded cells. Then there is a level of ${ℱ}_{ℐ}$ separating them outside of $B$. However, by definition, $x_{s^i}$ and $x_{s^j}$ must lie on the same side of any relevant level in ${ℱ}_{ℐ}$.

We thus indeed have that all the points $x_{s^1},\mathrm{\dots },x_{s^k}$ lie in a common unbounded cell of ${ℱ}_{ℐ}$ outside of $B$. Now we use the same argument as in the proof of Theorem 4. In particular, we can again find an embedding of the cube ${[-1,1]}^d$ where each face $F_I$ characterized by a subset $I\subseteq [d]$ lies in this common unbounded cell of ${ℱ}_{ℐ}$. After applying a homeomorphism on ${ℝ}^d$ that maps this embedding to the cube ${[-1,1]}^d\subset {ℝ}^d$ we can thus assume that all relevant levels of the color class $H_i$ have the facet $x_i=-1$ on their negative side, and the facet $x_i=1$ on their positive side.

We now take the same functions $f_i$ as in the proof of Theorem 4, which satisfy the conditions of the Poincaré-Miranda theorem. We thus get that there is a point $x^{\ast }$ in ${[-1,1]}^d$ for which $f_i(x^{\ast })=0$ for all $i\in \{1,\mathrm{\dots },d\}$. $◀$

We think that it is instructive to translate Theorem 13 back to the original setting of colored point sets in ${ℝ}^d$ (i.e., the primal setting). Note that in Definition 12, the condition that $x_s$ must lie in an unbounded face has technical reasons: In the proof of Theorem 13, it allows us to easily embed the cube that we need for the Poincaré-Miranda theorem. However, we can get away without this assumption in the case of (straight) hyperplanes: In that case, the $k$-levels are guaranteed to be connected and piecewise linear, and thus we can embed the cube without assuming that the points $x_s$ lie in unbounded faces. Therefore, when going to the primal setting, we can omit this technical assumption and define $(\beta ,\gamma )$-separation for point sets as follows.

By dualizing the point set and applying Theorem 13 for the dual hyperplanes, we thus get the following corollary for $(\beta ,\gamma )$-separated point sets.

This proof is illustrated in Figure 7. We start by drawing the four control lines as straight horizontal lines in the order (top to bottom) $r_{-1},r_0,r_{n+1},r_{n+2}$, making sure that the pairs $r_{-1},r_0$ and $r_{n+1},r_{n+2}$ are relatively close to each other while there is a big gap between $r_0$ and $r_{n+1}$. Next, we place $k$ points $p_1,\mathrm{\dots },p_k$ with increasing $x$-coordinates between $r_{-1}$ and $r_0$, and we place two points $q$ and $q^{\prime }$ with increasing $x$-coordinates between $r_{n+1}$ and $r_{n+2}$. The blue lines $b_i$ and $b_i^{\prime }$ are then drawn as straight lines where $b_i$ goes through $p_i$ and $q$, and $b_i^{\prime }$ goes through $p_i$ and $q^{\prime }$ for all $i\in [k]$. It remains to draw $r_1,\mathrm{\dots },r_n$ as pseudo-lines just below $r_0$. Note that just below $r_0$, the blue lines read as $b_1^{\prime },b_1,\mathrm{\dots },b_k^{\prime },b_k$ from left to right, which is what we need for our red pseudo-lines. Clearly, the red pseudo-lines can be drawn such as to ensure the proper intersections along each of the blue lines. It is not hard to see that this thus yields a well-separated rainbow arrangement. $◀$

Next, we prove that applying the construction to a YES-instance of allowable sequences yields a YES-instance of bicolored stretchability. The construction is similar to the proof of Lemma 18. The difference is that, by our assumption that we are given a YES-instance of allowable sequences, we can now ensure that all red lines are straight as well.

We take the line arrangement that realizes ${\pi }_1,\mathrm{\dots },{\pi }_k$ and color all $n$ lines red. Next, choose $k$ points $p_1,\mathrm{\dots },p_k$ above the arrangement with increasing $x$-coordinates, corresponding to the permutations ${\pi }_1,\mathrm{\dots },{\pi }_k$. In other words, by walking from $p_i$ vertically downward, we are guaranteed to observe the permutation ${\pi }_i$, for all $i\in [k]$. Moreover, we ensure that we will not observe any crossing of two red lines while walking vertically downward. This means that we could even walk at a very small angle (i.e., almost vertically) and still observe the correct permutation.

Next, we choose two points $q,q^{\prime }$ below the arrangement such that $q$ is to the left of $q^{\prime }$. By moving both $q$ and $q^{\prime }$ vertically down towards negative infinity, we can guarantee that for all $i\in [k]$, the straight blue line $b_i$ (or $b_i^{\prime }$, respectively) drawn through $p_i$ and $q$ (or $q^{\prime }$, respectively) observes the permutation ${\pi }_i$. It remains to draw the control lines:

• $\mathrm{■}$

  $r_{-1}$ is drawn as a horizontal line just above the points $p_1,\mathrm{\dots },p_k$,

• $\mathrm{■}$

  $r_0$ is drawn as a horizontal line just below $p_1,\mathrm{\dots },p_k$,

• $\mathrm{■}$

  $r_{n+1}$ is drawn as a horizontal line just above $q,q^{\prime }$,

• $\mathrm{■}$

  and $r_{n+2}$ is drawn horizontally just below $q,q^{\prime }$.

$◀$

It remains to prove the other direction, i.e., that a realization of the constructed instance of bicolored stretchability also implies a realization of the allowable sequences instance.

Consider the straight-line realization of the bicolored stretchability instance. By construction of the control lines $r_{-1}$ and $r_0$, $b_i$ and $b_i^{\prime }$ have to cross at a point $p_i$ that lies above the lines $r_1,\mathrm{\dots },r_n$ for all $i\in [k]$. Moreover, we know that the control line $r_{n+2}$ lies below the other lines and intersects the blue lines in the order $b_k,\mathrm{\dots },b_1,b_k^{\prime },\mathrm{\dots },b_1^{\prime }$. In particular, let $q$ be an arbitrary point on $r_{n+2}$ that lies in-between $b_1$ and $b_k^{\prime }$.

Next, for each $i\in [k]$, draw a new line $b_i^{\prime \prime }$ through $p_i$ and $q$. Observe that $b_i^{\prime \prime }$ intersects $r_{n+2}$ in $q$, and in particular $q$ lies between the intersections of $r_{n+2}$ with $b_i^{\prime }$ and $b_i$, respectively. Since $b_i$ and $b_i^{\prime }$ intersect $r_1,\mathrm{\dots },r_n$ in the same order (given by ${\pi }_i$), so does $b_i^{\prime \prime }$. This means that each of the lines $b_i^{\prime \prime }$ observes the correct permutation, and they all pass through the same point $q$ that lies on $r_{n+2}$. Thus, we can apply a projective transformation that turns $r_{n+2}$ into the line at infinity, which in turn ensures that the lines $b_1^{\prime \prime },\mathrm{\dots },b_k^{\prime \prime }$ are parallel. We conclude that the red lines $r_1,\mathrm{\dots },r_n$ after the transformation are a realization of the original allowable sequences instance. $◀$

Putting all of this together, we conclude that bicolored stretchability is indeed $\exists ℝ$-complete.

We argued that it is contained in $\exists ℝ$ by using the verification-approach in [13]. $\exists ℝ$-hardness follows from our reduction from allowable sequences above, where correctness follows from combining Lemma 19 and Lemma 20. $◀$

Certainly, Theorem 21 also implies $\exists ℝ$-hardness for the realizability problem of more general two-colored rainbow arrangements (that are not necessarily well-separated). Concretely, this also implies that realizability of bicolored order types (that were studied in, e.g., [2]) is $\exists ℝ$-hard. However, the well-separation condition is useful for us, as it allows us to also conclude that realizability of grid USO⁷⁷7A grid USO is called realizable if it is induced by an instance of the P-Matrix Generalized Linear Complementarity Problem (PGLCP). We do not elaborate on the details of realizability of grid USOs here and instead rely on prior work that establishes the appropriate connection with hyperplane arrangements [10]. is $\exists ℝ$-complete.

Note that containment in $\exists ℝ$ follows again by giving a real-RAM verifier, and we will not go into the details of this. Instead, we explain why USO realizability is $\exists ℝ$-hard based on prior work: It was proven in [10] that realizable grid USOs correspond to well-separated hyperplane arrangements. This allows us to reduce bicolored stretchability to realizability of two-dimensional grid USO: Given the well-separated rainbow arrangement, construct the orientation as described in Section 2. This must yield a two-dimensional grid USO. If this grid USO is realizable, then by [10] there exists a well-separated line arrangement corresponding to this grid USO, which hence must have the same combinatorial description as the initial well-separated rainbow arrangement. Conversely, any well-separated line arrangement with the same combinatorial information implies that the constructed orientation is realizable. $◀$