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 study the common intersection of arrangements of double-wedges. We consider arrangements where double-wedges may be both bowties (which do not contain a vertical line) or hourglasses (which contain a vertical line), in contrast to earlier studies that focused on arrangements of only bowties. This generalization changes the setting drastically, in particular, with respect to all arguments involving the point-line duality. Namely, a point in the intersection of all double-wedges is equivalent to a line that stabs a set of segments S (corresponding to the bowties) while it avoids a different set of segments A (corresponding to the complement of the hourglasses). We show that in this general setting, the intersection of n double-wedges may consist of Ω( n 2 ) interior-disjoint regions. Further, we discuss Gallai-type results for arrangements of segments and anti-segments, and we provide algorithms for computing the intersection of such arrangements with worst-case optimal running time. Finally, we also prove that we can find a single intersection point in almost optimal running time, assuming that 3SUM admits no truly subquadratic-time algorithm.

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 Necklace Splitting problem is a classical problem in combinatorics that has been intensively studied both from a combinatorial and a computational point of view. It is well-known that the Necklace Splitting problem reduces to the discrete Ham Sandwich problem. This reduction was crucial in the proof of PPA-completeness of the Ham Sandwich problem. Recently, Borzechowski, Schnider and Weber [ISAAC'23] introduced a variant of Necklace Splitting that similarly reduces to the $α$-Ham Sandwich problem, which lies in the complexity class UEOPL but is not known to be complete. To make this reduction work, the input necklace is guaranteed to be n-separable. They showed that these necklaces can be fairly split in polynomial time and thus this subproblem cannot be used to prove UEOPL-hardness for $α$-Ham Sandwich. We consider the more general unfair necklace splitting problem on n-separable necklaces, i.e., the problem of splitting these necklaces such that each thief gets a desired fraction of each type of jewels. This more general problem is the natural necklace-splitting-type version of $α$-Ham Sandwich, and its complexity status is one of the main open questions posed by Borzechowski, Schnider and Weber. We show that the unfair splitting problem is also polynomial-time solvable, and can thus also not be used to show UEOPL-hardness for $α$-Ham Sandwich.

Let P be a set of n = 2 m + 1 points in the plane in general position. We define the graph G M P whose vertex set is the set of all plane matchings on P with exactly m edges. Two vertices in G M P are connected if the two corresponding matchings have m − 1 edges in common. In this work we show that G M P is connected and give an upper bound of O ( n 2 ) on its diameter. Moreover, we present a lower bound of n − 2 and an upper bound of 2 n − 2 for the diameter of G M P for P in convex position.

We show that each set of n ⩾ 2 points in the plane in general position has a straight-line matching with at least ( 5 n + 1 ) / 27 edges whose segments form a connected set, and such a matching can be computed in O ( n log ⁡ n ) time. As an upper bound, we show that for some planar point sets in general position the largest matching whose segments form a connected set has ⌈ n − 1 3 ⌉ edges. We also consider a colored version, where each edge of the matching should connect points with different colors.

Schaefer's dichotomy theorem [Schaefer, STOC'78] states that a boolean constraint satisfaction problem (CSP) is polynomial-time solvable if one of six given conditions holds for every type of constraint allowed in its instances. Otherwise, it is NP-complete. In this paper, we analyze boolean CSPs in terms of their topological complexity, instead of their computational complexity. We attach a natural topological space to the set of solutions of a boolean CSP and introduce the notion of projection-universality. We prove that a boolean CSP is projection-universal if and only if it is categorized as NP-complete by Schaefer's dichotomy theorem, showing that the dichotomy translates exactly from computational to topological complexity. We show a similar dichotomy for SAT variants and homotopy-universality.

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.

Abstract For sets of n points, n even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least $$C_{n/2}$$ C n / 2 different plane perfect matchings, where $$C_{n/2}$$ C n / 2 is the n /2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have k crossings. We show the following results. (1) For every $$k\le \frac{1}{64}n^2-\frac{35}{32}n\sqrt{n}+\frac{1225}{64}n$$ k ≤ 1 64 n 2 - 35 32 n n + 1225 64 n , any set with n points, n sufficiently large, admits a perfect matching with exactly k crossings. (2) There exist sets of n points where every perfect matching has at most $$\frac{5}{72}n^2-\frac{n}{4}$$ 5 72 n 2 - n 4 crossings. (3) The number of perfect matchings with at most k crossings is superexponential in n if k is superlinear in n . (4) Point sets in convex position minimize the number of perfect matchings with at most k crossings for $$k=0,1,2$$ k = 0 , 1 , 2 , and maximize the number of perfect matchings with $$\left( {\begin{array}{c}n/2\\ 2\end{array}}\right) $$ n / 2 2 crossings and with $${\left( {\begin{array}{c}n/2\\ 2\end{array}}\right) }\!-\!1$$ n / 2 2 - 1

Abstract Let P be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in P. We say two points $$a,b\in P$$ a , b ∈ P can see each other if the line segment $${\text {seg}} (a,b)$$ seg ( a , b ) is contained in P. We denote by V(P) the family of all minimum guard placements. The Hausdorff distance makes V(P) a metric space and thus a topological space. We show homotopy-universality, that is, for every semi-algebraic set S there is a polygon P such that V(P) is homotopy equivalent to S. Furthermore, for various concrete topological spaces T, we describe instances I of the art gallery problem such that V(I) is homeomorphic to T.

Regression depth, introduced by Rousseeuw and Hubert in 1999, is a notion that measures how good of a regression hyperplane a given query hyperplane is with respect to a set of data points. Under projective duality, this can be interpreted as a depth measure for query points with respect to an arrangement of data hyperplanes. The study of depth measures for query points with respect to a set of data points has a long history, and many such depth measures have natural counterparts in the setting of hyperplane arrangements. For example, regression depth is the counterpart of Tukey depth. Motivated by this, we study general families of depth measures for hyperplane arrangements and show that all of them must have a deep point. Along the way we prove a Tverberg-type theorem for hyperplane arrangements, giving a positive answer to a conjecture by Rousseeuw and Hubert from 1999. We also get three new proofs of the centerpoint theorem for regression depth, all of which are either stronger or more general than the original proof by Amenta, Bern, Eppstein, and Teng. Finally, we prove a version of the center transversal theorem for regression depth.

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].

In this paper, we disprove the long-standing conjecture that any complete geometric graph on 2n vertices can be partitioned into n plane spanning trees. Our construction is based on so-called bumpy wheel sets. We fully characterize which bumpy wheels can and in particular which cannot be partitioned into plane spanning trees (or even into arbitrary plane subgraphs). Furthermore, we show a sufficient condition for generalized wheels to not admit a partition into plane spanning trees, and give a complete characterization when they admit a partition into plane spanning double stars. Finally, we initiate the study of partitions into beyond planar subgraphs, namely into k-planar and k-quasi-planar subgraphs and obtain first bounds on the number of subgraphs required in this setting.

isomorphism classes of line arrangements).It can be decided in polynomial time whether an allowable sequence is realizable by an arrangement of approaching pseudo-lines. Furthermore, arrangements of approaching pseudo-lines can be transformed into each other by flipping triangular cells, i.e., they have a connected flip graph, and every bichromatic arrangement of this type contains a bichromatic triangular cell.

We consider the following problem: Let L be an arrangement of n lines in R3 in general position colored red, green, and blue. Does there exist a vertical plane P such that a line in P simultaneously bisects all three classes of points induced by the intersection of lines in L with P? Recently, Schnider used topological methods to prove that such a cross-section always exists. In this work, we give an alternative proof of this fact, using only methods from discrete geometry. With this combinatorial proof at hand, we devise an O(n2log2⁡(n)) time algorithm to find such a plane and a bisector of the induced cross-section. We do this by providing a general framework, from which we expect that it can be applied to solve similar problems on cross-sections and kinetic points.

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 paper 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.

The centerpoint theorem is a well-known and widely used result in discrete geometry. It states that for any point set P of n points in R^d, there is a point c, not necessarily from P, such that each halfspace containing c contains at least n/(d+1) points of P. Such a point c is called a centerpoint, and it can be viewed as a generalization of a median to higher dimensions. In other words, a centerpoint can be interpreted as a good representative for the point set P. But what if we allow more than one representative? For example in one-dimensional data sets, often certain quantiles are chosen as representatives instead of the median. We present a possible extension of the concept of quantiles to higher dimensions. The idea is to find a set Q of (few) points such that every halfspace that contains one point of Q contains a large fraction of the points of P and every halfspace that contains more of Q contains an even larger fraction of P. This setting is comparable to the well-studied concepts of weak epsilon-nets and weak epsilon-approximations, where it is stronger than the former but weaker than the latter. We show that for any point set of size n in R^d and for any positive alpha_1,...,alpha_k where alpha_1 <= alpha_2 <= ... <= alpha_k and for every i,j with i+j <= k+1 we have that (d-1)alpha_k+alpha_i+alpha_j <= 1, we can find Q of size k such that each halfspace containing j points of Q contains least alpha_j n points of P. For two-dimensional point sets we further show that for every alpha and beta with alpha <= beta and alpha+beta <= 2/3 we can find Q with |Q|=3 such that each halfplane containing one point of Q contains at least alpha n of the points of P and each halfplane containing all of Q contains at least beta n points of P. All these results generalize to the setting where P is any mass distribution. For the case where P is a point set in R^2 and |Q|=2, we provide algorithms to find such points in time O(n log^3 n).