  A family of $k$ point sets in $d$ dimensions is well-separated if the convex
hulls of any two disjoint subfamilies can be separated by a hyperplane.
Well-separation is a strong assumption that allows us to conclude that certain
kinds of generalized ham-sandwich cuts for the point sets exist. But how hard
is it to check if a given family of high-dimensional point sets has this
property? Starting from this question, we study several algorithmic aspects of
the existence of transversals and separations in high-dimensions.
  First, we give an explicit proof that $k$ point sets are well-separated if
and only if their convex hulls admit no $(k - 2)$-transversal, i.e., if there
exists no $(k - 2)$-dimensional flat that intersects the convex hulls of all
$k$ sets. It follows that the task of checking well-separation lies in the
complexity class coNP. Next, we show that it is NP-hard to decide whether there
is a hyperplane-transversal (that is, a $(d - 1)$-transversal) of a family of
$d + 1$ line segments in $\mathbb{R}^d$, where $d$ is part of the input. As a
consequence, it follows that the general problem of testing well-separation is
coNP-complete. Furthermore, we show that finding a hyperplane that maximizes
the number of intersected sets is NP-hard, but allows for an
$\Omega\left(\frac{\log k}{k \log \log k}\right)$-approximation algorithm that
is polynomial in $d$ and $k$, when each set consists of a single point. When
all point sets are finite, we show that checking whether there exists a $(k -
2)$-transversal is in fact strongly NP-complete.
