Computational Complexity of the $α$-Ham-Sandwich Problem

Introduction

There are many alternative and more general variants of both the continuous and the discrete Ham-Sandwich Theorem. For example, Bárány and Matoušek [BM01] derived a version where measures in the plane can be divided into any (possibly different) ratios by fans instead of hyperplanes (lines). A discrete variant of this result was given by Bereg [Ber05]. Schnider [Sch19a] studied a generalization in higher dimensions. Recently Barba, Pilz, and Schnider [BPS19] showed that four measures in the plane can be bisected with two lines. Zivaljević and Vrećica [ZV90] proved a result that interpolates between the Ham-Sandwich Theorem and the Centerpoint Theorem [Rad46], of which there is also a no-dimensional version [CM20]. Schnider [Sch19b] presented a generalization based on this result among others.

Steiger and Zhao called their result the Generalized Ham-Sandwich Theorem, yet it is not a strict generalization of the classic Ham-Sandwich Theorem. Their result requires that the point sets obey well-separation and weak general position, while the classic theorem always holds without these assumptions. Therefore, we call this result the $\alpha$-Ham-Sandwich theorem, for a clearer distinction. Set $n=\sum_{i\in[d]}|S_{i}|$. Steiger and Zhao gave an algorithm that computes the dividing hyperplane in $O\left(n(\log n)^{d-3}\right)$ time, which is exponential in $d$. Later, Bereg [Ber12] improved this algorithm to achieve a running time of $n2^{O(d)}$, which is linear in $n$ but still exponential in $d$. We denote the associated computational search problem of finding the dividing hyperplane as Alpha-HS.

No polynomial algorithms are known for Ham-Sandwich and for Alpha-HS if the dimension is not fixed, and the notion of approximation is also not well-explored. Despite their superficial similarity, it is not immediately apparent whether the two problems are comparable in terms of their complexity. Due to the additional requirements on an input for Alpha-HS, an instance of Ham-Sandwich may not be reducible to Alpha-HS in general.

Since a dividing hyperplane for Alpha-HS is guaranteed to exist if the sets satisfy the conditions of well-separation and (weak) general position, Alpha-HS is a total search problem. In general, such problems are modelled by the complexity class $\mathsf{TFNP}$ (Total Function Nondeterministic Polynomial) of $\mathsf{NP}$-search problems that always admit a solution. Two popular subclasses of $\mathsf{TFNP}$, originally defined by Papadimitriou [Pap94], are $\mathsf{PPA}$ (Polynomial Parity Argument) its sub-class $\mathsf{PPAD}$. These classes contain total search problems where the existence of a solution is based on a parity argument in an undirected or in a directed graph, respectively. Another sub-class of $\mathsf{TFNP}$ is $\mathsf{PLS}$ (polynomial local search). It models total search problems where the solutions can be obtained as minima in a local search process, while the number of steps in the local search may be exponential in the input size. The class $\mathsf{PLS}$ was introduced by Johnson, Papadimitriou, and Yannakakis [JPY88]. A noteworthy sub-class of $\mathsf{PPAD}\cap\mathsf{PLS}$ is $\mathsf{CLS}$ (continuous local search) [DP11]. It models similar local search problems over a continuous domain using a continuous potential function.

Up to very recently, these complexity classes have mostly been studied in the context of algorithmic game theory. However, there have been increasing efforts towards mapping the complexity landscape of existence theorems in high-dimensional discrete geometry. Computing an approximate solution for the search problem associated with the Borsuk-Ulam Theorem is in $\mathsf{PPA}$. In fact, this problem is complete for this class. The discrete analogue of the Borsuk-Ulam Theorem, Tucker’s Lemma [Tuc46], is also $\mathsf{PPA}$-complete [ABB20]. Therefore, since the traditional proof of the Ham-Sandwich Theorem goes through the Borsuk-Ulam Theorem, it follows that Ham-Sandwich lies in $\mathsf{PPA}$. In fact, Filos-Ratsikas and Goldberg [FRG19] recently showed that Ham-Sandwich is complete for $\mathsf{PPA}$. The (presumably smaller) class $\mathsf{PPAD}$ is associated with fixed-point type problems: computing an approximate Brouwer fixed point is a prototypical complete problem for $\mathsf{PPAD}$. The discrete analogue of Brouwer’s Fixed Point Theorem, Sperner’s Lemma, is also complete for $\mathsf{PPAD}$. In a celebrated result, the relevance of $\mathsf{PPAD}$ for algorithmic game theory was made clear when it turned out that computing a Nash-equilibrium in a two player game is $\mathsf{PPAD}$-complete [CDT09]. In discrete geometry, finding a solution to the Colorful Carathéodory problem [Bár82] was shown to lie in the intersection $\mathsf{PPAD}\cap\mathsf{PLS}$ [MMSS17, MS18]. This further implies that finding a Tverberg partition (and computing a centerpoint) also lies in the intersection [Tve66, Sar92, LGMM19]. The problem of computing the (unique) fixed point of a contraction map is known to lie in $\mathsf{CLS}$ [DP11].

Recently, at ICALP 2019, Fearley, Gordon, Mehta, and Savani defined a sub-class of $\mathsf{CLS}$ that represents a family of total search problems with unique solutions [FGMS19]. They named the class Unique End of Potential Line ($\mathsf{UEOPL}$) and defined it through the canonical complete problem UniqueEOPL. This problem is modelled as a directed graph. There are polynomially-sized Boolean circuits that compute the successor and predecessor of each node, and a potential value that always increases on a directed path. There is supposed to be only a single vertex with no predecessor (start of line). Under these conditions, there is a unique path in the graph that ends on a vertex (called end of line) with the highest potential along the path. This vertex is the solution to UniqueEOPL. Since the uniqueness of the solution is guaranteed only under certain assumptions, such a formulation is called a promise problem. Since there seems to be no efficient way to verify the assumptions, the authors allow two possible outcomes of the search algorithm: either report a correct solution, or provide any solution that was found to be in violation of the assumptions. This formulation turns UniqueEOPL into a non-promise problem and places it in $\mathsf{TFNP}$, since a correct solution is bound to exist when there are no violations, and otherwise a violation can be reported as a solution. Fearley et al. [FGMS19] also introduced the concept of a promise-preserving reduction between two problems $A$ and $B$, such that if an instance of $A$ has no violations, then the reduced instance of $B$ is also free of violations. This notion is particularly meaningful for non-promise problems.

Contributions.

We provide the first non-trivial containment in a complexity class for the $\alpha$-Ham-Sandwich problem by locating it in $\mathsf{UEOPL}$. More precisely, we formulate Alpha-HS as a non-promise problem in which we allow for both valid solutions representing the correct dividing hyperplane, as well as violations accounting for the lack of well-separation and/or (weak) general position of the input point sets. A precise formulation of the problem is given in Definition 4 in Section 2. We then show a promise-preserving reduction from Alpha-HS to UniqueEOPL. This implies that Alpha-HS lies in $\mathsf{UEOPL}$, and hence in $\mathsf{CLS}\subseteq\mathsf{PPAD}\cap\mathsf{PLS}$. See Figure 2 for a pictorial description.

It is not surprising to discover that Alpha-HS lies in $\mathsf{PPAD}$, since the proof of the continuous version in [BHJ08] was based on Brouwer’s Fixed Point Theorem. The observation that it also lies in $\mathsf{PLS}$ is new and noteworthy, putting Alpha-HS into the reach of local search algorithms. In contrast, given our current understanding of total search problems, it is unlikely that the problem Ham-Sandwich would be in $\mathsf{PLS}$.

Since Alpha-HS lies in $\mathsf{PPAD}\subseteq\mathsf{PPA}$, it is computationally easier than Ham-Sandwich, which is $\mathsf{PPA}$-complete. This implies the existence of a polynomial-time reduction from Alpha-HS to Ham-Sandwich. A reduction in the other direction is unlikely. It thus turns out that well-separation brings down the complexity of the problem by a significant amount.

Often, problems in $\mathsf{TFNP}$ come in the guise of a polynomial-size Boolean circuit with some property. In contrast, Alpha-HS is a purely geometric problem that has no circuit in its problem definition. This is the second problem in $\mathsf{UEOPL}$ apart from the $P$-Matrix Linear complementarity problem and one of the few in $\mathsf{CLS}$ that does not have a description in terms of circuits.

Our local-search formulation is based on the intuition of rotating a hyperplane until we reach the desired solution. We essentially start with a hyperplane that is tangent to the convex hull of each input set, and we deterministically rotate the hyperplane until it hits a new point. This rotation can be continued whenever the hyperplane hits a new point, until we reach the correct dividing hyperplane. In other words, we can follow a local-search argument to find the solution. We show that this sequence of rotations can be modelled as a canonical path in a grid graph, and we give a potential function that guides the rotation and always increases along this path. Every violation of well-separation and (weak) general position can destroy this path. Furthermore, no efficient methods to verify these two assumptions are known. This poses a major challenge in handling the violations. One of our main technical contributions is to handle the violation solutions concisely.

An alternative approach would have been to look at the dual space of points where we get an arrangement of hyperplanes. The dividing hyperplane could then be found by looking at the correct level sets of the arrangement. However, this approach has the problem that the orientations of the hyperplanes in the original space and the dual space are not consistent. This complicates the arguments on the level sets, so we found it more convenient to use our notion of rotating hyperplanes. We show that we can maintain a consistent orientation throughout the rotation, and an inconsistent rotation is detected as a violation of the promise.

Outline of the paper.

We discuss the background about the $\alpha$-Ham-sandwich Theorem and UniqueEOPL in Section 2. In Section 3, we describe our instance of Alpha-HS and give an overview of the reduction and violation-handling. The technical details of the reduction are presented in Section 4 and Section 5. We conclude in Section 6.

Preliminaries

For conciseness, we describe the discrete version of $\alpha$-Ham-Sandwich Theorem [SZ10] here. The continuous version [BHJ08] follows a similar formulation.

We say that $P$ has very weak general position [SZ10], if for every choice of points $x_{1}\in P_{1},\dots,x_{d}\in P_{d}$, the affine hull of the set $\{x_{1},\dots,x_{d}\}$ is a $(d-1)$-flat and does not contain any other point of $P$. This definition is sufficient for the result of Steiger and Zhao, where they simply call it as weak general position. Of course, this definition of weak general position has no restriction on sets $\{x_{1},\dots,x_{d}\}$ that contain multiple points from the same color. To simplify our proofs we need a slightly stronger form of general position. We say that $P$ has weak general position if the above restriction also applies to sets having exactly $d-1$ colors. That means, each color may contribute at most one point to the set, except perhaps one color which is allowed to contribute two points. A certificate for checking violations of weak general position is a set of $d+1$ points whose affine hull has dimension at most $d-1$, with at least $d-1$ colors in the set. Testing whether a planar point set is in general position can be shown to be $\mathsf{NP}$-Hard, using the result in [FKNN17]. It is easy to see that when $d=2$, weak general position is equivalent to general position.

Well-separation.

A certificate for checking violations of well-separation is a colorful set $\{x_{1},\dots,x_{d}\}$ whose affine hull has dimension at most $d-2$. Another certificate is a partition $I,J\subset[d]$ such that the convex hulls of the indexed sets are not separable. Due to Lemma 1, both certificates are equivalent and either can be converted to the other in polynomial time. To the best of our knowledge, the complexity of testing well-separation is unknown.

Given any set of positive integers $\{\alpha_{1},\dots,\alpha_{d}\}$ satisfying $1\leq\alpha_{i}\leq n_{i}$, $i\in[d]$, an $(\alpha_{1},\dots,\alpha_{d})$-cut is an oriented hyperplane $H$ that contains one point from each color and satisfies $|H^{+}\cap P_{i}|=\alpha_{i}$ for $i\in[d]$, where $H^{+}$ is the closed positive half-space defined by $H$.

If an $\alpha$-cut exists, then it is unique.

If $P$ has weak general position, then a cut exists for each choice of $\alpha$, $\alpha_{i}\in[n_{i}]$.

That means, every colorful $d$-tuple of $P$ corresponds to exactly one $\alpha$-vector. Steiger and Zhao [SZ10] also presented an algorithm to compute the cut in $O(n(\log n)^{d-3})$ time, where $n=\sum_{i=1}^{d}n_{i}$. The algorithm proceeds inductively in dimension and employs a prune-and-search technique. Bereg [Ber12] improved the pruning step to improve the runtime to $n2^{O(d)}$.

2 Unique End of Potential Line

We briefly explain the Unique end of potential line problem that was introduced in [FGMS19]. More details about the problem and the associated class can be found in the above reference.

Let $n,m$ be positive integers. The input consists of

The complexity class $\mathsf{UEOPL}$ represents the class of problems that can be reduced in polynomial time to UniqueEOPL. This has been shown to lie in $\mathsf{CLS}$ in [FGMS19] and contains three classical problems: finding the fixed point of a contraction map, solving the P-Matrix Linear complementarity problem, and finding the unique sink of a directed graph (with arbitrary edge orientations) on the 1-skeleton of a hypercube.

A notion of promise-preserving reductions is also defined in [FGMS19]. Let $X$ and $Y$ be two problems both having a formulation that allows for valid and violation solutions. A reduction from $X$ to $Y$ is said to be promise-preserving, if whenever it is promised that $X$ has no violations, then the reduced instance of $Y$ also has no violations. Thus a promise-preserving reduction to UniqueEOPL would mean that whenever the original problem is free of violations, then the reduced instance always has a single line that ends at a valid solution.

3 Formulating the search problem

We formalize the search problem for $\alpha$-Ham-Sandwich in a non-promise setting:

A subset of $P$ of size $d+1$ and at least $d-1$ colors that lies on a hyperplane.

Here a solution of type (G1) corresponds to a solution representing a valid cut, while solutions of type (GV1) and (GV2) refer to violations of weak general position and well-separation, respectively. From Theorem 2 we see that a valid solution is guaranteed if no violations are presented, which shows that Alpha-HS is a total search problem.

Alpha-HS is in UEOPL

In this section we describe our instance of Alpha-HS in more detail and briefly outline a reduction to UniqueEOPL.

1 An overview of the reduction

We give a short overview of the ideas used in the reduction from Alpha-HS to UniqueEOPL. The details are technical and we defer them to Section 5. We encourage the interested reader to go through the details of our reduction.

Our intuition is based on rotating a colorful hyperplane $H$ to another colorful hyperplane $H^{\prime}$ through a sequence of local changes of the points on the hyperplanes such that the $\alpha$-vector of $H^{\prime}$ increases in some coordinate by one from that of $H$. We next define the rotation operation in a little more detail. An anchor is a colorful $(d-1)$-tuple of $P$ which spans a $(d-2)$-flat. The following procedure takes as input an anchor $R$ and some point $p\in P\setminus R$ and determines the next hyperplane obtained by a rotation. The output is $(R^{\prime},p^{\prime})$, where $R^{\prime}$ is an anchor and $p^{\prime}\in P\setminus R^{\prime}$ is some point.

Procedure $(R^{\prime},p^{\prime})=NextRotate(R,p)$

Let $H$ denote the hyperplane defined by $R\cup\{p\}$ and $t_{1}$ be the missing color in $R$.

If the orientation of $H$ is not well-defined, report a violation of weak general position and well-separation.

Let $P^{+}_{t_{1}}$ be the subset of $P_{t_{1}}$ that lies in the closed halfspace $H^{+}$ and $P^{-}_{t_{1}}$ be the subset of $P_{t_{1}}$ that lies in the open halfspace $H^{-}$. Let $x\in P^{+}_{t_{1}}$ be the highest ranked point according to the order $\prec_{t_{1}}$ and $y\in P^{-}_{t_{1}}$ be the highest ranked point according to $\prec_{t_{1}}$.

If $p$ has color $t_{1}$ and $|P^{+}_{t_{1}}|=n_{t_{1}}$, report out of range.

We rotate $H$ around the anchor $R$ in a direction such that the hyperplane is moving away from $x$ along the segment $xy$ until it hits some point $q\in P$.

If the hyperplane hits multiple points at the same time, report a violation of weak general position.

If $p^{\prime}$ is not color $t_{1}$, set $R^{\prime}:=R\cup\{q\}\setminus\{r\}$ and $p^{\prime}=r$, where $r$ is a point in $R$ with the same color as $p^{\prime}$. Otherwise, set $R^{\prime}=R$ and $p^{\prime}=q$.

Figure 3 shows an application of this procedure, rotating $H_{0}$ to $H_{4}$ through $H_{1},H_{2},H_{3}$.

This rotation function can be interpreted as a function that assigns each hyperplane to the next hyperplane. The set of colorful hyperplanes can be interpreted as vertices in a graph with the rotation function determining the connectivity of the graph.

Each colorful hyperplane $H$ is incident to a colorful set of $d$ points. This set of points defines $d$ possible anchors, and each anchor can be used to rotate $H$ in a different fashion. To define a unique sequence of rotations, we pick a specific order as follows: first, we assume that the colorful hyperplane $H$ whose $\alpha$-vector is $(1,\ldots,1)$ is given (we show later how this assumption can be removed). We start at $H$ and pick the anchor that excludes the first color, then apply a sequence of rotations until we hit another colorful hyperplane with $\alpha$-vector $(2,1,\ldots,1)$. Similarly, we move to a colorful hyperplane with $\alpha$-vector $(3,1,\ldots,1)$ and so on until we reach $(\alpha_{1},1,\ldots,1)$. Then, we repeat this for the other colors in order to reach $(\alpha_{1},\alpha_{2},1,\ldots,1)$ and so on until we reach the target $\alpha$-vector. This pattern of $\alpha$-vectors helps in defining a potential function that strictly increases along the path. We can encode this sequence of rotations as a unique path in the UniqueEOPL instance, and we call it canonical path.

A natural way to define the UniqueEOPL graph would be to consider hyperplanes as the vertices in the graph. However, this leads to complications. Figure 3 shows a rotation from $H_{0}$ to $H_{4}$, with $\alpha$-vectors $(2,3)$ and $(3,3)$ respectively. During the rotation, we encounter a hyperplane $H_{2}$ for which its $\alpha$-vector is $(2,4)$, which differs from our desired sequence of $(2,3),\dots,(2,3),(3,3)$. This makes it difficult to define a potential function in the graph that strictly increases along the path $v_{H_{0}},\dots,v_{H_{4}}$ where $v_{H_{i}}$ is the vertex representing hyperplane $H_{i}$. One way to alleviate this problem is to not use $H_{i}$ as a vertex directly, but the double-wedge that is traced out by the rotation from $H_{i}$ to $H_{i+1}$. If the $\alpha$-vector is now measured using the hyperplane that bisects the double-wedge, then we get the desired sequence of $(2,3),\dots,(2,3),(3,3)$. See Figure 3 for an example.

With additional overhead, the rotation function can be extended to double-wedges. This in turn also leads to a neighborhood graph where the vertices are the double-wedges and the rotations can be used to define the edges. The graph is connected and has a grid-like structure that may be of independent interest. To simplify the exposition, we postpone the description of double-wedges and the associated graph to Section 4.

Distance parameter and potential function.

The $\alpha$-vector is not sufficient to define the potential function, since the sequence of rotations between two colorful hyperplanes may have the same $\alpha$-vector. For instance, the bisectors of the rotations in $H_{0},\dots,H_{3}$ in Figure 3 all have the same $\alpha$-vector. Hence, we need an additional measurement in order to determine the direction of rotation that increases the $\alpha$-vector.

Similar to how we define the orientation for a non-colorful hyperplane, let $H$ denote a hyperplane that passes through points of $(d-1)$ colors. Let $P_{j}$ denote the missing color in $H$. Let $x,y\in P_{j}$ be the highest ranked points under $\prec_{j}$ in $H^{+}$ and $H^{-}$ respectively. Let $z$ denote the intersection of $xy$ and $H$. We define a distance parameter called dist-value of $H$ to be the distance $\|x-z\|$. In Figure 3, we can see that rotating from $H_{0}$ to $H_{4}$ sweeps the segment $xy$ in one direction, with the dist-value of the hyperplanes increasing strictly. This is sufficient to break ties and hence determine the correct direction of rotation. The precise statement is given in Lemma 6. We can extend this definition to the domain of double-wedges. We define a potential value for each vertex on the canonical path in UniqueEOPL using the sum of weighed components of $\alpha$-vector and dist-value for the tie-breaker.

Correctness.

We show that if there are no violations, we can always apply Procedure $NextRotate$ to increment the $\alpha$-vector until we find the desired solution, which implies that the canonical path exists. If the input satisfies weak general position, we can see that the rotating hyperplane always hits a unique point in Step $5$, which may be swapped to form a new anchor in Step $7$.

The well-separation condition guarantees that the potential function always increases along the rotation. Let $H_{1},H_{2}$ denote a pair of hyperplanes that are the input and output of Procedure $NextRotate$ respectively. Let $H$ denote any intermediate hyperplane during the rotation from $H_{1}$ to $H_{2}$ through the common anchor. Let $P_{j}$ be the color missing from the anchor and $x$ be the highest ranked point under $\prec_{j}$ in $H_{1}^{+}$. We say that the orientation of $H_{2}$ (resp. $H$) is consistent with that of $H_{1}$ if $x\in H_{2}^{+}$ (resp. $x\in H^{+}$). Lemma 5 shows that the orientations are always consistent when $H_{1}$ and $H_{2}$ are non-colorful hyperplanes even without the assumption of well-separation.

Assume that weak general position holds. Let $H_{1},H_{2}$ be the input and output of Procedure $NextRotate$ respectively. Let $H$ denote any intermediate hyperplane within the rotation. The orientations of $H_{1}$ (resp. $H_{2}$) and $H$ are consistent when $H_{1}$ (resp. $H_{2}$) is a non-colorful hyperplane.

Since $H_{1}$ is a non-colorful hyperplane, let $P_{j}$ denote the color missing from $H_{1}$. $H_{1}$ and $H$ give the same partition of $P_{j}$ into two sets because the continuous rotation from $H_{1}$ to $H$ does not hit any point in $P_{j}$. Let $x$ and $y$ be the highest ranked points under $\prec_{j}$ in each set. Since we have weak general position, the segment $xy$ cannot pass through the anchor of the rotation so that the orientations of $H_{1}$ and $H$ are well-defined by the $(d-1)$ colored points in the anchor and the intersections of the hyperplanes with the segment $xy$. Thus, the determinant defining the normal of the rotating hyperplane from $H_{1}$ to $H$ for the orientation is always non-zero. Since the intersection of the rotating hyperplane from $H_{1}$ to $H$ and the segment $xy$ moves continuously along $xy$, by a continuity argument, the normal of the hyperplane does not flip during the rotation. Without loss of generality, assume that $x\in H_{1}^{+}$. This implies that $x$ is always in the positive half-space of $H$ and hence $H$ has a consistent orientation as $H_{1}$. The same proof holds for $H_{2}$. ∎

Next, we show that the dist-value is strictly increasing for all the intermediate hyperplanes in the sequence of rotations from one colorful hyperplane to another colorful hyperplane.

Assume that weak general position holds. Let $H_{0}$ be a colorful hyperplane and $H_{k}$ be the first colorful hyperplane obtained by a sequence of rotations by Procedure $NextRotate$. We denote $H_{1},\ldots,H_{k-1}$ be the non-colorful hyperplanes obtained from the above sequence of rotations. The dist-values of $H_{1},\ldots,H_{k-1}$ is strictly increasing.

Let $P_{j}$ denote the color missing from $H_{1}$. Then, $H_{2},\ldots,H_{k-1}$ all miss the color $P_{j}$, otherwise $H_{k}$ is not the first colorful hyperplane obtained by the rotations. Therefore, each $H_{i}$ gives the same partition of $P_{j}$ into two sets for $i=1,\ldots,k-1$ because the continuous rotations from $H_{1}$ to $H_{k-1}$ does not hit any point in $P_{j}$. Let $x$ and $y$ be the highest ranked points under $\prec_{j}$ in each set. Without loss of generality, assume that $x\in H_{1}^{+}$. Since $H_{1},\ldots,H_{k-1}$ are non-colorful hyperplanes, by Lemma 5, the consistent of the orientation can carry from $H_{1}$ to $H_{2}$ and so on. Then we have $x\in H_{1}^{+},\dots,x\in H_{k-1}^{+}$ and $y\in H_{1}^{-},\dots,y\in H_{k-1}^{-}$. Let $z_{1}=xy\cap H_{1},\dots,z_{k-1}=xy\cap H_{k-1}$. According to Step $5$ of Procedure $NextRotate$, each rotation is performed by moving away from $x$ along the segment $xy$. Hence we have $\|x-z_{1}\|<\|x-z_{2}\|<\dots<\|x-z_{k-1}\|$. ∎

The last step for proving that the potential function always increases along the canonical path is to show that the $\alpha$-vector increases in some coordinate from one colorful hyperplane to another colorful hyperplane through Procedure $NextRotate$. This requires the assumption of well-separation. Lemma 7 shows that if the orientations of $H_{1},H_{2}$ and $H$ are inconsistent, then well-separation is violated. By the contrapositive, if well-separation is satisfied, then all hyperplanes in the rotation always give consistent orientations. Then, it implies that rotating from a colorful hyperplane $H_{0}$ to another colorful hyperplane $H_{k}$ through a sequence of non-colorful hyperplanes that miss color $P_{j}$, we have $H_{0}^{+}\cap P_{j}\subset H_{k}^{+}\cap P_{j}$ and $H_{k}$ contains one additional point in $P_{j}$ that is hit by the last rotation. Therefore, $\alpha_{j}$ is increased by $1$ and other $\alpha_{i}$s keep the same value because of the way we swap the point of repeated color with the one in the anchor and the direction of rotation.

Since the orientations of $H_{1}$ and $H$ are inconsistent, $H_{1}$ must be a colorful hyperplane by Lemma 5. Therefore, the point in $H_{1}$ that is not in the anchor is in $P_{j}$, denoted by $p$.

In order to guarantee that there is no other path in UniqueEOPL apart from the canonical path, we introduce self-loops for vertices that are not on the canonical path. The detailed proof is given in Lemma 17 that if there are no violations, then the reduced instance of UniqueEOPL only gives a (U1) solution, which readily translates to a (G1) solution, so our reduction is promise-preserving, and this can be done in polynomial time.

Since we do not know the hyperplane with $\alpha$-vector $(1,\dots,1)$ in advance, we split the problem into two sub-problems: in the first we start with any colorful hyperplane. We reverse the direction of the canonical path determined by the potential and construct an Alpha-HS instance for which the vertex with $\alpha$-vector $(1,\dots,1)$ is the solution. In the second, we use this vertex as the input to the main Alpha-HS instance. If the input is free of violations, then both sub-problems give valid solutions and together they answer the original question.

Handling violations.

The reduction maps violations of Alpha-HS to those of the UniqueEOPL instance, and certificates for the violations can be recovered from additional processing. When a violation of weak general position is witnessed on a vertex that lies on the canonical path, a hyperplane incident to $d$ colors may contain additional points. This in turn implies that some $\alpha$-cut is missing, so that the correct solution for the target may not exist. In addition, the (highest-ranked) points $x,y$ from the missing color that we choose to define the orientation of a non-colorful hyperplane may form a segment $xy$ that passes through the $(d-2)$-flat spanned by the anchor. In that case the orientation of the hyperplane is not well-defined. In the reduction, these problematic vertices are removed from the canonical path, thereby creating some additional starting points and end points in the reduced instance. These violations can be captured by (U1) with a wrong $\alpha$-vector or (UV2). Furthermore, the hyperplanes that contains the degenerate point sets could be represented by different choices of anchors and a additional point on the plane. Each such pair represents a vertex in the reduced instance. We join these vertices in the form of a cycle in the UniqueEOPL instance with all vertices having the same potential value, so that the violations can also be captured by (UV1) and (UV3).

When a violation of well-separation is witnessed on a vertex on the canonical path, the orientations of the two hyperplanes paired by Procedure $NextRotate$ may be inconsistent, which may not guarantee that the $\alpha$-vector is incremented in one component by one (See Figure 4). Hence, the canonical path is split into two paths that can be captured by (UV2). Furthermore, a violation of well-separation also creates multiple colorful hyperplanes with the same $\alpha$-vector (See Figure 4, left). Two vertices in the UniqueEOPL graph with the same potential value, which could correspond to some colorful or non-colorful hyperplanes, can be reported by (UV3). We show that this gives a certificate of violation of well-separation in the following lemmata, where $m_{0}$ is the number of bits used to represent each coordinate of points of $P$.

Let $p_{1}\in P_{1},\ldots,p_{d}\in P_{d}$ denote the colorful points on $H_{p}$ and $q_{1}\in P_{1},\ldots,q_{d}\in P_{d}$ denote the colorful points on $H_{q}$. Throughout this proof, we consider $H^{+}$ to be a closed halfspace while $H^{-}$ is an open halfspace. We prove the claim by induction on the dimension $d$.

Without loss of generality, suppose that the open segment $p_{1}q_{1}\in H_{p}^{-}\cap H_{q}^{+}$. Since $p_{1}\in H_{p}^{+}\cap H_{q}^{+}$ and $q_{1}\in H_{p}^{-}\cap H_{q}^{+}$, there exists at least one point $r_{1}\in P_{1}\cap(H_{p}^{+}\cap H_{q}^{-})$ in order for $|P_{1}\cap H_{p}^{+}|=|P_{1}\cap H_{q}^{+}|$ to hold. If the open segment $p_{2}q_{2}$ also lies in $H_{p}^{-}\cap H_{q}^{+}$ (resp. $H_{p}^{+}\cap H_{q}^{-}$), then there exists at least one point $r_{2}$ in $P_{2}\cap(H_{p}^{+}\cap H_{q}^{-})$ (resp. $P_{2}\cap(H_{p}^{-}\cap H_{q}^{+})$). We can see that the intersection point $x$ of $H_{p}$ and $H_{q}$ lies inside the triangles $\triangle p_{1}q_{1}r_{1}$ and $\triangle p_{2}q_{2}r_{2}$ (see Figure 11(b)).

Suppose that the open segment $p_{2}q_{2}$ lies in $H_{p}^{+}\cap H_{q}^{+}$ (resp. $H_{p}^{-}\cap H_{q}^{-}$). In order to assign correct orientations to $H_{p}$ and $H_{q}$, the order in which points of $P_{1}$ and $P_{2}$ appears on the hyperplanes along any direction must be the same for both. This is only feasible when $p_{2}$ lies between $p_{1}$ (resp. $q_{1}$) and the intersection point $x=H_{p}\cap H_{q}$. Hence, $p_{2}$ (resp. $q_{2}$) lies inside the triangles $\triangle p_{1}q_{1}r_{1}$ (see Figure 11(c)).

The idea is to transform $P$ to a point set $P^{\prime}$, in which we can find two points from the missing color that can each be moved onto one of the non-colorful hyperplanes. Then, the two non-colorful hyperplanes become colorful hyperplanes in $P^{\prime}$ with the same $\alpha$-vector so that we are in the setup of Lemma 8 and the claim follows.

Without loss of generality, we assume that the missing color of the two non-colorful hyperplanes is color 1. Let $H_{p}$ denote one of the non-colorful hyperplanes that passes through some $p_{2}\in P_{2},\ldots,p_{d}\in P_{d}$ and $H_{q}$ denote another non-colorful hyperplane that passes through some $q_{2}\in P_{2},\ldots,q_{d}\in P_{d}$. Recall that they have the same $\alpha$-vector and dist-value. Let $x_{p},y_{p}$ (resp. $x_{q},y_{q}$) be the highest ranked points of $P_{1}$ under $\prec_{1}$ on either side of $H_{p}$ (resp. $H_{q}$) and let $z_{p}$ (resp. $z_{q}$) be the intersection of segment $x_{p}y_{p}$ (resp. $x_{q}y_{q}$) with $H_{p}$ (resp. $H_{q}$). By the definition and assumption of dist-value, the dist-value of $H_{p}$ and $H_{q}$ is $||x_{p}-z_{p}||=||x_{q}-z_{q}||$.

In the following, we consider the case of $x_{p},x_{q}\in H_{p}^{+}\cap H_{q}^{+}$ with three sub-cases:

$[y_{p}\in H_{p}^{-}\cap H_{q}^{-}\mbox{ and }y_{q}\in H_{p}^{+}\cap H_{q}^{-}]$: the argument is symmetrical to the case above.

$[y_{p}\in H_{p}^{-}\cap H_{q}^{+}\mbox{ and }y_{q}\in H_{p}^{+}\cap H_{q}^{-}]$: we move $y_{p}$ towards $x_{p}$ along segment $x_{p}y_{p}$ until it hits $H_{p}$ and move $y_{q}$ towards $x_{q}$ along segment $x_{q}y_{q}$ until it hits $H_{q}$.

Next, we consider $x_{p}\in H_{p}^{+}\cap H_{q}^{+}$ and $x_{q}\in H_{p}^{-}\cap H_{q}^{+}$.

$[y_{p}\in H_{p}^{-}\cap H_{q}^{+}\mbox{ and }y_{q}\in H_{p}^{-}\cap H_{q}^{-}]$: we have $x_{q}=y_{p}$. We move $x_{p}$ towards $x_{q}$ along segment $x_{p}x_{q}$ until it hits $H_{p}$ and move $x_{q}$ towards $y_{q}$ along segment $x_{q}y_{q}$ until it hits $H_{q}$.

$[y_{p}\in H_{p}^{-}\cap H_{p}^{-}\mbox{ and }y_{q}\in H_{p}^{+}\cap H_{q}^{-}]$: we move $x_{p}$ towards $x_{q}$ along segment $x_{p}x_{q}$ until it hits $H_{p}$ and move $x_{q}$ towards $y_{p}$ along segment $x_{q}y_{p}$ until it hits $H_{q}$.

$[y_{p}\in H_{p}^{-}\cap H_{q}^{+}\mbox{ and }y_{q}\in H_{p}^{+}\cap H_{q}^{-}]$: we have $x_{q}=y_{p}$. We move $y_{p}$ towards $x_{p}$ along segment $x_{p}y_{p}$ until it hits $H_{p}$ and move $y_{q}$ towards $x_{p}$ along segment $x_{p}y_{q}$ until it hits $H_{q}$.

$[y_{p}\in H_{p}^{-}\cap H_{q}^{-}\mbox{ and }y_{q}\in H_{p}^{-}\cap H_{q}^{-}]$: we have $y_{p}=y_{q}$. We move $x_{p}$ towards $x_{q}$ along segment $x_{p}x_{q}$ until it hits $H_{p}$ and move $x_{q}$ towards $y_{q}$ along segment $x_{q}y_{q}$ until it hits $H_{q}$.

The case for $x_{p}\in H_{p}^{+}\cap H_{q}^{-}$ and $x_{q}\in H_{p}^{+}\cap H_{q}^{+}$ are symmetrical to those above.

The last case is $x_{p}\in H_{p}^{+}\cap H_{q}^{-}$ and $x_{q}\in H_{p}^{-}\cap H_{q}^{+}$. Basically, the sub-cases are the same as those above except one, which happens for $y_{p}\in H_{p}^{-}\cap H_{p}^{+}$ and $y_{q}\in H_{p}^{+}\cap H_{q}^{-}$. In this case, we have $x_{p}=y_{q}$ and $x_{q}=y_{p}$. We move $x_{p}$ and $x_{q}$ towards each other along segment $x_{p}x_{q}$ and until they hit $H_{p}$ and $H_{q}$. Note that the segment $x_{p}x_{q}$ may intersect the $(d-2)$-flat $H_{p}\cap H_{q}$, but this case is also handled by Lemma 8. ∎

Alpha-HS $\in$ $\mathsf{UEOPL}$ $\subseteq$ $\mathsf{CLS}$.

Double-wedges and the neighborhood graph

In this section we formally define the notion of double-wedges and the underlying graph that is defined using rotations.

An anchor is a colorful $(d-1)$-tuple of $P$ which spans a $(d-2)$-flat. Let $P_{i}$ denote the missing color in the anchor. Then the tuple for the anchor $R=(p_{1},\dots,p_{d-1})$ is ordered as $R=\{p_{1}\in P_{1},\dots,p_{i-1}\in P_{i-1},p_{i}\in P_{i+1},\dots,p_{d-1}\in P_{d}\}$. An anchor $R$ along with a pair of points $p,q\in P$ such that $p,q\not\in R$ is called a double-wedge if all of the following hold:

the hyperplane $H_{p}$ through $R\cup\{p\}$ does not contain $q$. This implies that the hyperplane $H_{q}$ through $R\cup\{q\}$ does not contain $p$.

if $x,y$ are the highest ordered points of $P_{i}$ under $\prec_{i}$ on either sides of $H_{p},H_{q}$, then $R\cup\{x,y\}$ does not lie on a hyperplane.

the intersection of the open halfspaces $H_{q}^{+}\cap H_{p}^{-}$ is empty, that is, it does not contain any point of $P$. Similarly $H_{p}^{+}\cap H_{q}^{-}$ must also be empty.

We visualize the anchor as a $(d-2)$-ridge through which $H_{p},H_{q}$ pass through. A rotation around the anchor changes one hyperplane to the other without passing through any other point of $P$. Intuitively the double-wedge refers to the space $(H_{q}^{+}\cap H_{p}^{-})\cup(H_{p}^{+}\cap H_{q}^{-})$ and we use this interpretation several times. See Figure 5 for a simple example.

For a double-wedge $w:=(R,p,q)$, we define a representative hyperplane $H_{w}$ as the hyperplane that is the angular bisector of the double-wedge. Since a double-wedge is empty, $H_{w}$ does not contain any point of $P$ apart from $R$. We define an orientation for $H_{w}$ based on $R$ and the color missing from $R$. Let $x,y$ be points from the missing color as defined before. Without loss of generality, let $x\in H_{w}^{+}$, and $y\in H_{w}^{-}$. We call the first hyperplane among $H_{p},H_{q}$ that intersects the directed segment $xy$ as the upper hyperplane of $w$ and the other hyperplane as the lower hyperplane of $w$. A simple example can be found in Figure 6.

The $\alpha$-vector of any oriented hyperplane $H$ is a $d$-tuple $(a_{1},\dots,a_{d})$ of integers where $a_{i}$ is the number of points of $P_{i}$ in the closed halfspace $H^{+}$ for $i\in[d]$. The $\alpha$-vector of a double-wedge $w=(R,p,q)$ is defined as the $\alpha$-vector of its representative hyperplane. We say that a double-wedge $w=(R,p,q)$ is non-colorful, if both $R\cup\{p\}$ and $R\cup\{q\}$ are non-colorful, and colorful, if exactly one of $R\cup\{p\}$ and $R\cup\{q\}$ is colorful, and very colorful, if both $R\cup\{p\}$ and $R\cup\{q\}$ are colorful.

Under the assumption of weak general position, we additionally have that if $w$ is non-colorful, then $H_{p},H_{q}$ are non-colorful, and if $w$ is colorful, exactly one of $H_{p},H_{q}$ is colorful, and if $w$ is very colorful, both $H_{p},H_{q}$ are colorful.

The definition of dist-value for hyperplanes can be extended to double-wedges by setting the dist-value of a double-wedge as that of its representative hyperplane. Consequently, the results of Lemmas 5, 6 and 7 extend to double-wedges with simple modifications.

2 Defining a neighborhood graph

We define a concept of neighborhood between double-wedges, and then we use this to define a graph whose vertices correspond to the double-wedges. We first describe the graph under the assumptions that the colors are well-separated and $P$ is in weak general position. Later we show how to handle the cases when these assumptions fail.

We call two double-wedges $(R,p,q),(R^{\prime},p^{\prime},q^{\prime})$ neighboring if both share a common hyperplane, that is, $\{H_{p},H_{q}\}\cap\{H_{p^{\prime}},H_{q^{\prime}}\}\neq\varnothing$, with an exception that we elaborate below. A double-wedge $w=(R,p,q)$ has different number of neighbors depending on how colorful its hyperplanes are. The anchor can be written in the form $R=\{x_{1},\dots,x_{d-1}\}$.

Let $w$ be non-colorful. Then $p,q$ both share their colors with those of $R$. Suppose $p$ has the same color as $x_{i}$. Then there are at most three neighboring double-wedges that share $H_{p}$. One of them use the same anchor $R$, and as an exception we do not count this as a neighboring double-wedge. For the two remaining neighbors, the anchor is $R^{\prime}=(x_{1},\dots,p,\dots,x_{d-1})$ where $p$ has replaced $x_{i}$. The two rotational directions determine the two double-wedges. Only one of them has the same $\alpha$-vector as $w$, since the representative hyperplanes contain $x_{i}$ on opposite sides. With a similar argument, there are at most two neighboring double-wedges that share $H_{q}$ and at most one of them has the same $\alpha$-vector as $w$.

Let $w$ be colorful, where $H_{p}$ is colorful and $H_{q}$ is non-colorful, without loss of generality. By replacing some $x_{i}$ by $p$ we get an anchor that is contained in $H_{p}$ and which may define a double-wedge for each of the two rotational directions. Since there are $(d-1)$ possible anchors formed by replacement, there are at most $2(d-1)$ double-wedges that share $H_{p}$. Additionally, keeping the anchor $R$ fixed, there is at most one neighboring double-wedge. So there are at most $2d-1$ neighboring double-wedges of $w$ that share $H_{p}$. The case for $H_{q}$ is similar to case (1).

Let $w$ be very colorful. Similar to case (2), there are at most $2d-1$ double-wedges sharing $H_{p}$. The case for $H_{q}$ is similar.

We build a graph $G$ where each vertex corresponds to a double-wedge. Let $w=(R,p,q)$ be any double-wedge. For simplicity, we denote the vertex in $G$ corresponding to $w$ also by $w$. If $H_{p}$ is colorful, we add an edge in $G$ between $w$ and the vertex of each neighboring double-wedge that shares $H_{p}$. If $H_{p}$ is non-colorful, we add an edge only with the vertex of the double-wedge that shares its $\alpha$-vector with that of $w$. Thus, non-colorful double-wedges have degree two in $G$, while colorful and very colorful double-wedges have degrees at most $2d$ and $4d-2$, respectively.

We transfer each attribute of a double-wedge to its vertex in $G$. For instance, we call vertices of $G$ as non-colorful, colorful or very colorful corresponding to the color of the double-wedge representing the vertex. Similarly, each vertex has an $\alpha$-vector that corresponds to the $\alpha$-vector of its double-wedge, and so on. See Figure 7 for an elementary example.

Let $v\in G$ be any vertex and let $(\alpha_{1},\dots,\alpha_{d})$ denote the $\alpha$-vector of $v$. The largest $\alpha$-vector for any hyperplane is $(n_{1},\dots,n_{d})$ that occurs on a unique tangent hyperplane whose half-space contains $P$. With our definition of the $\alpha$-vector of double-wedges using the representative hyperplanes, for any double-wedge $w$, the $\alpha$-vector of $w$ is smaller in at least one coordinate from the maximum.

Let $H$ be a colorful hyperplane with $\alpha$-vector $(\alpha_{1},\dots,\alpha_{d})$. For each $j\in[d]$, if $\alpha_{j}\leq n_{j}-1$ (resp. $\alpha_{j}\geq 2$), then there is a path $w,w_{1},w_{2},\dots,w_{k},w^{\prime}$ in $G$ such that the double-wedge $w$ is incident to $H$, the double-wedge $w^{\prime}$ is incident to another colorful hyperplane $H^{\prime}$, $w,w_{1},w_{2},\dots,w_{k}$ share the same $\alpha$-vector and the $\alpha$-vector for $H^{\prime}$ differs only in the $j$-th component, where the value is $\alpha_{j}+1$ (resp. $\alpha_{j}-1$).

For the case that $\alpha_{j}\leq n_{j}-1$, we set an anchor $R$ in $H$ that excludes the $j$-th colored point, say $p_{j}$. Then, we apply Procedure $NextRotate$ starting from $(R,p_{j})$ until we get another colorful hyperplane $H^{\prime}$. Let $w$ be the double-wedge created by the first rotation. Note that $p_{j}$ is on the upper hyperplane of $w$. During this sequence of rotations, we also get a sequence of double-wedges. Before the rotating hyperplane $H^{\prime\prime}$ hits a point $p_{i}$ of repeated color $i$, assume that $p_{i}$ is in the negative half-space of $H^{\prime\prime}$. Once $p_{i}$ is on $H^{\prime\prime}$, we swap $p_{i}$ with another point $p^{\prime}_{i}$ of the same color in the anchor and keep the rotation towards the opposite direction of the orientation so that $p_{i}$ is in the positive half-space of $H^{\prime\prime}$ and $p^{\prime}_{i}$ from the positive half-space moves to the negative half-space. This is true because the orientation is consistent by Lemma 5. If $p_{i}$ is in the positive half-space of $H^{\prime\prime}$ before $p_{i}$ is hit by $H^{\prime\prime}$, then $p_{i}$ remains in the positive half-space and $p^{\prime}_{i}$ as well (see Figure 3). Both cases maintain $\alpha_{i}$ during the rotation. Thus, all non-colorful double-wedges in this sequence of rotations have the same $\alpha$-vector as $w$. In the last rotation, the rotating hyperplane hits the first point $p^{\prime}_{j}$ of color $j$. By Lemma 7, well-separation guarantees the consistency of the orientation of the rotating hyperplane so that $p^{\prime}_{j}$ moves from the negative half-space to the positive half-space and other points of color $j$ remain in the same sides of the hyperplane. Thus, $\alpha_{j}$ is increased by one. The same argument also works for the case that $\alpha_{j}\geq 2$ by using the inverse of Procedure $NextRotate$.

Since all the double-wedges created by the first rotation for each $j$ are incident to $H$, they are also connected in $G$ by definition. ∎

By Lemma 12, we know that all (very) colorful double-wedges are connected. For non-colorful double-wedges, we apply Procedure $NextRotate$ on its lower hyperplane until the rotating hyperplane hits some point of the missing color, which implies that non-colorful double-wedges also connect to some (very) colorful double-wedge. ∎

The neighborhood graph $G$ imitates a grid in a coarse sense. There is a ”vertex” for every colorful $d$-tuple of $P$, and there are paths connecting these grid vertices. We showed in Lemma 13 that $G$ is connected. Therefore, given a target $\alpha$-vector $(\alpha_{1},\dots,\alpha_{d})$, the correct $d$-tuple can be found by starting from some vertex and walking towards the solution. See Figure 8 for an illustration.

If $P$ violates well-separation or weak general position, then many nice properties of the neighborhood graph are destroyed. Double-wedges may fail to have consistent orientations by Lemma 7. There may be multiple solutions for the same $\alpha$-cut, and no solutions for other cuts. The former case will manifest as multiple vertices with the same $\alpha$-vector, but they may lie in different connected components, so Lemma 13 will fail, making the graph disconnected. For the latter case, there will be no vertex in $G$ that corresponds to the $\alpha$-cut. The grid-like structure exhibited in Lemma 12 is also not applicable anymore, meaning that the canonical path may not exist. See Figure 9 for a graph that contains violations.

The formal reduction

As shown in Section 3, a vertex $v$ in $\cal I^{\prime}$ corresponds to $(R,p,q)$ in $\cal I$, where $R$ is a colorful point set of size $(d-1)$ from $P$, and $p,q\in P$. We are only interested in the case when $(R,p,q)$ is a double-wedge, as per the definition in Section 4.1. Otherwise, we create a self loop on $v$ in $\cal{I^{\prime}}$. Furthermore, if there are no violations in $\cal I$, we can define a canonical path from the vertex $v_{0}$ with $\alpha$-vector $=(1,\ldots,1)$ to the unique vertex $v_{\alpha}$ with $\alpha$-vector $=(\alpha_{1},\dots,\alpha_{d})$ (shown in Section 3.1), which is the unique path in $\cal I^{\prime}$. For other vertices $v$ not on the path, we also create a self loop on $v$. For instance, when $\cal I$ fails weak general position assumption, then $R\cup\{p_{1},p_{2},\ldots,p_{m}\}$ lie on the same hyperplane, where $p_{1}\prec\dots\prec p_{m}\in P$. In this case we create a cycle on $v_{1}=(R,p_{1},q),v_{2}=(R,p_{2},q),\ldots,v_{m}=(R,p_{m},q)$ with the same potential value on each $v_{i}$, so that this violation may be reported as the violation (UV1) in $\cal I^{\prime}$. When $\cal I$ fails the well-separated assumption, the graph we constructed may contain more than one path, which may be reported as the violations (UV2) or (UV3) in $\cal I^{\prime}$. In particular, if a hyperplane witnesses both the violations of weak general position and well-separation, then the cycle may become a path with the same potential value, so any violation could be possible.

$t_{1}$ contains $\lceil\log d\rceil$ bits representing the index of the missing color in $R$,

$t_{2},\ldots,t_{d}$ each contain $\lceil\log n_{0}\rceil$ bits for the indices of the points in $R$ ordered by $\prec$,

$(t_{d+1},t_{d+2})$ contain $\lceil\log d\rceil$ and $\lceil\log n_{0}\rceil$ bits for the index of the color and the index of $p\in P_{t_{d+1}}$ respectively,

and we use the same idea to represent $q$ by $(t_{d+3},t_{d+4})$. Altogether, we need at most $\kappa=3\cdot\lceil\log d\rceil+(d+1)\cdot\lceil\log n_{0}\rceil$ bits in the encoding. Let $f_{v}:\{P\}^{d+1}\rightarrow\{0,1\}^{\kappa}$ denote the function that encodes $(R,p,q)$ to $(t_{1},\ldots,t_{d+4})$. If $(R,p,q)$ is a double-wedge, then $(R,q,p)$ also represents the same double-wedge. Since we do not want to create two valid vertices in $G$ corresponding to the same double-wedge, we only pick the one with $(t_{d+1},t_{d+2})$ on the upper hyperplane as a valid double-wedge. The following lemma details how we can verify whether a given encoding $(t_{1},\ldots,t_{d+4})$ is a double-wedge:

The rotation process is handled by procedures $NextNeighbor$ and $PrevNeighbor$, which we describe next. Let $w=(R,p,q)$ be the current double-wedge. Some abnormal cases may happen in the output $w^{\prime}=(R^{\prime},p^{\prime},q^{\prime})$ of $NextNeighbor$ or $PrevNeighbor$ when the segment $xy$ that defines the orientation of $H_{w^{\prime}}$ passes through $R^{\prime}$ (see Figure 10), $H_{p^{\prime}}$ or $H_{q^{\prime}}$ contains more than $d$ points, or the orientations of $H_{p^{\prime}},H_{q^{\prime}},H_{w^{\prime}}$ are not consistent. For these cases, the path will end or start at $w$. When UniqueEOPL outputs $w$, we can compute $w^{\prime}$ and find the certificate of a violation as follows: for the first or second case, it is easy to see that it violates well-separation and/or weak general position. For the third case, we show that it violates well-separation and that we can obtain a certificate for the violation in Lemma 7.