Enclosing Depth and Other Depth Measures

Medians are an important tool in the statistical analysis and visualization of data. Due to the fact that medians only depend on the order of the data points, and not their exact positions, they are very robust against outliers. However, in many applications, data sets are multidimensional, and there is no clear order of the data set. For this reason, various generalizations of medians to higher dimensions have been introduced and studied, see e.g. [1, 20, 25] for surveys. Many of these generalized medians rely on a notion of depth of a query point within a data set, a median then being a query point with the highest depth among all possible query points. Several such depth measures have been introduced over time, most famously Tukey depth [35] (also called halfspace depth), simplicial depth [19], or convex hull peeling depth (see, e.g., [1]). In particular, just like the median, all of these depth measures only depend on the relative positions of the involved points. More formally, let \(S^{{\mathbb {R}}^d}\) denote the family of all finite sets of points in \({\mathbb {R}}^d\). A depth measure is a function \(\varrho : (S^{{\mathbb {R}}^d},{\mathbb {R}}^d)\rightarrow {\mathbb {R}}_{\ge 0}\) which assigns to each pair (S, q) consisting of a finite set of data points S and a query point q a value, which describes how deep the query point q lies within the data set S. A depth measure \(\varrho \) is called combinatorial if it depends only on the order type of \(S\cup \{q\}\). The order type of a point set \(S=\{s_1,\ldots ,s_n\}\) is a mapping that assigns to each ordered \((d+1)\)-tuple of points the orientation of the spanned simplex. Another way to view this is the following: consider all hyperplanes spanned by d or more points of S. This defines an arrangement A of hyperplanes, whose cells are the connected components of \({\mathbb {R}}^d\setminus A\). Then all points in a cell have the same depth.

In this paper, we consider general classes of combinatorial depth measures, defined by a small set of axioms, and prove relations between them and concrete depth measures, such as Tukey depth (\(\text {TD}\)) and Tverberg depth (\(\text {TvD}\)). Let us first briefly discuss these two depth measures.

Definition 1

Let S be a finite point set in \({\mathbb {R}}^d\) and let q be a query point. Then the Tukey depth of q with respect to S, denoted by \({\textbf {TD}}(S,q)\), is the minimum number of points of S in any closed half-space containing q.

Tukey depth, also known as halfspace depth, was independently introduced by Joseph L. Hodges in 1955 [13] and by John W. Tukey in 1975 [35] and has received significant attention since Tukey’s paper, both from a combinatrial as well as from an algorithmic perspective, see e.g. Chapter 58 in [34] and the references therein. Notably, Rado’s centerpoint theorem states that for any point set \(S\subset {\mathbb {R}}^d\), there exists a point \(q\in {\mathbb {R}}^d\) for which \(\text {TD}(S,q)\ge \frac{|S|}{d+1}\) [27].

In order to define Tverberg depth, we need a preliminary definition: given a point set S in \({\mathbb {R}}^d\), an r-partition of S is a partition of S into r pairwise disjoint subsets \(S_1,\ldots ,S_r\subset S\) with \(\bigcap _{i=1}^r\text {conv}(S_i)\ne \emptyset \). We call \(\bigcap _{i=1}^r\text {conv}(S_i)\) the intersection of the r-partition.

Definition 2

Let S be a finite point set in \({\mathbb {R}}^d\) and let q be a query point. Then the Tverberg depth of q with respect to S, denoted by \({\textbf {TvD}}(S,q)\), is the maximum r such that there is an r-partition of S whose intersection contains q.

Tverberg depth is named after Helge Tverberg who proved in 1966 that any set of \((d+1)(r-1)+1\) points in \({\mathbb {R}}^d\) allows an r-partition [36]. In particular, this implies that there is a point q with \(\text {TvD}(S,q)\ge \frac{|S|}{d+1}\). Just as for Tukey depth, there is an extensive body of work on Tverberg’s theorem, see the survey [5] and the references therein.

In \({\mathbb {R}}^1\), both Tukey and Tverberg depth give a very natural depth measure: it counts the number of points of S to the left and to the right of q and then returns the minimum of the two numbers. We call this measure the standard depth in \({\mathbb {R}}^1\). In particular, for all of them there is always a point \(q\in {\mathbb {R}}^1\) for which we have \(\varrho (S,q)\ge \frac{|S|}{2}\), that is, a median.

Another depth measure that is important in this paper is called enclosing depth. We say that a point set S of size \((d+1)k\) in \({\mathbb {R}}^d\) k-encloses a point q if S can be partitioned into \(d+1\) pairwise disjoint subsets \(S_1,\ldots ,S_{d+1}\), each of size k, in such a way that for every transversal \(p_1\in S_1,\ldots , p_{d+1}\in S_{d+1}\), the point q is in the convex hull of \(p_1,\ldots ,p_{d+1}\). If the sizes of \(S_1,\ldots , S_{d+1}\) are not specified, we just say that \(S_1,\ldots ,S_{d+1}\) enclose q. Intuitively, if \(S\cup \{q\}\) is in general position, the points of S are centered around the vertices of a simplex with q in its interior. More formally, as we will see in Sect. 4, the convex hulls of the \(S_i\) are well-separated, meaning that for each \(I\subseteq \{1,\ldots ,d+1\}\) the convex hulls of \(\bigcup _{i\in I}S_i\) and \(\bigcup _{i\notin I}S_i\) can be separated by a hyperplane through q.

Definition 3

Let S be a finite point set in \({\mathbb {R}}^d\) and let q be a query point. Then the enclosing depth of q with respect to S, denoted by \({\textbf {ED}}(S,q)\), is the maximum k such that there exists a subset of S which k-encloses q.

It is straightforward to see that enclosing depth also gives the standard depth in \({\mathbb {R}}^1\). The centerpoint theorem [27] and Tverberg’s theorem [36] show that both for Tukey as well as Tverberg depth, there are deep points in any dimension. The question whether a depth measure enforces deep points is a central question in the study of depth measures. It turns out that this also holds for enclosing depth. In fact, Fabila-Monroy and Huemer [10] have shown that enclosing depth can be bounded from below by a constant fraction of Tukey depth. We give a new proof of this fact, which gives a slightly better constant. We will further show that all depth measures considered in this paper can be bounded from below by enclosing depth. From this we get one of the main results of this paper: all depth measures that satisfy the axioms given later are a constant factor approximation of Tukey depth.

Another area of study in depth measures are depth regions, also called depth contours. For some depth measure \(\varrho \) and \(\alpha \in {\mathbb {R}}\), we define the \(\alpha \)-region of a point set \(S\subset {\mathbb {R}}^d\) as the set of all points in \({\mathbb {R}}^d\) that have depth at least \(\alpha \) with respect to S. We denote the \(\alpha \)-region of S by \(D_{\varrho }^S(\alpha ):=\{q\in {\mathbb {R}}^d\mid \varrho (S,q)\ge \alpha \}\). Note that for \(\alpha <\beta \) we have \(D_{\varrho }^S(\alpha )\supset D_{\varrho }^S(\beta )\), that is, the depth regions are nested. The structure of depth regions has been studied for several depth measures, see e.g. [24, 40]. For example, it is well-known that Tukey depth regions are compact and convex. Depth regions in \({\mathbb {R}}^2\) have been proposed as a tool for data visualization [35]. From a combinatorial point of view, Gil Kalai introduced the following conjecture [15].

Conjecture 4

(Cascade Conjecture) Let S be a point set of size n in \({\mathbb {R}}^d\). For each \(i\in \{1,\ldots ,n\}\), denote by \(t_i\) the dimension of \(D_{\text {TvD}}^S(i)\), where we set \(\dim (\emptyset )=-1\). Then

Here, the dimension of a subset X of \({\mathbb {R}}^d\) is the maximum dimension of any neighborhood of a point in X. The conjecture is known to be true when S is in so-called strongly general position [28], for general position in some dimensions [30,31,32] (see also [5] for more information), and without any assumption of general position for \(d\le 2\) in an unpublished M. Sc thesis in Hebrew by Kadari (see [17]).

While Kalai’s conjecture is specifically about Tverberg depth, the sum of dimensions of depth regions can be computed for any depth measure, and thus the conjecture can be generalized to other depth measures. In fact, in a talk Kalai conjectured that the Cascade conjecture is true for Tukey depth, mentioning on his slides that ‘this should be doable’ [16]. In this work, we will prove the conjecture to be true for a family of depth measures that includes Tukey depth.

1.1 Structure of the Paper

We start the technical part by introducing a first set of axioms in Sect. 2, defining what we call super-additive depth measures. We show that these depth measures lie between Tukey depth and Tverberg depth. In Sect. 3 we prove the cascade conjecture for super-additive depth measures whose depth regions are compact and convex. We then give a second set of axioms in Sect. 4, defining central depth measures, and show how to bound them from below by enclosing depth. Finally, in Sect. 5, we give a new proof of a lower bound for enclosing depth in terms of Tukey depth. In our proof, we notice a close relationship of enclosing depth with a version of Radon’s theorem on certain two-colored point sets.

The first set of depth measures that we consider are super-additive depth measures.^{Footnote 1} A combinatorial depth measure \(\varrho : (S^{{\mathbb {R}}^d},{\mathbb {R}}^d)\rightarrow {\mathbb {R}}_{\ge 0}\) is called super-additive if it satisfies the following conditions:

1. (i)

   for all \(S\in S^{{\mathbb {R}}^d}\) and \(q,p\in {\mathbb {R}}^d\) we have \(|\varrho (S,q)-\varrho (S\cup \{p\},q)|\le 1\) (sensitivity),

2. (ii)

   for all \(S\in S^{{\mathbb {R}}^d}\) and \(q\in {\mathbb {R}}^d\) we have \(\varrho (S,q)=0\) for \(q\not \in \text {conv}(S)\) (locality),

3. (iii)

   for all \(S\in S^{{\mathbb {R}}^d}\) and \(q\in {\mathbb {R}}^d\) we have \(\varrho (S,q)\ge 1\) for \(q\in \text {conv}(S)\) (non-triviality),

4. (iv)

   for any disjoint subsets \(S_1,S_2\subseteq S\) and \(q\in {\mathbb {R}}^d\) we have \(\varrho (S,q)\ge \varrho (S_1,q)+\varrho (S_2,q)\) (super-additivity).

It is not hard to show that a one-dimensional depth measure which satisfies these conditions has to be the standard depth measure (in fact, the arguments are generalized to higher dimensions in the following two observations) and that no three conditions suffice for this. Further, it can be shown that both Tukey depth and Tverberg depth are super-additive.

We first note that the first two axioms suffice to give an upper bound:

Observation 5

For every depth measure \(\varrho \) satisfying (i) sensitivity and (ii) locality and for all \(S\in S^{{\mathbb {R}}^d}\) and \(q\in {\mathbb {R}}^d\) we have \(\varrho (S,q)\le \text {TD}(S,q)\).

Proof

By the definition of Tukey depth, \(\text {TD}(S,q)=k\) implies that we can remove a subset \(S'\) of k points from S so that q is not in the convex hull of \(S\setminus S'\). In particular, \(\varrho (S\setminus S',q)=0\) by locality. By sensitivity we further have \(\varrho (S\setminus S',q)\ge \varrho (S,q)-k\), which implies the claim. \(\square \)

Further, the last two axioms can be used to give a lower bound:

Observation 6

For every depth measure \(\varrho \) satisfying (iii) non-triviality and (iv) super-additivity and for all \(S\in S^{{\mathbb {R}}^d}\) and \(q\in {\mathbb {R}}^d\) we have \(\varrho (S,q)\ge \text {TvD}(S,q)\).

Proof

Let \(\text {TvD}(S,q)=k\) and consider a k-partition \(S_1,\ldots ,S_k\) with q in its intersection. By non-triviality we have \(\varrho (S_i,q)\ge 1\) for each \(S_i\). Using super-additivity and induction we conclude that \(\varrho (\bigcup _{i=1}^k S_i,q)\ge \sum _{i=1}^k\varrho (S_i,k)\ge k\). \(\square \)

Finally, it is not too hard to show that \(\text {TvD}(S,q)\ge \frac{1}{d}\text {TD}(S,q)\): consider a simplex \(\Delta \) spanned by points in S which contains q. Such a simplex exists by Carathéodory’s theorem. As \(\Delta \) has at most \(d+1\) vertices and q lies in its relative interior, any halfspace with q on its boundary contains at most d of the vertices of \(\Delta \). Thus, removing \(\Delta \) the Tukey depth decreases by at most d. While the Tukey depth is not 0, we can always find another simplex containing q, and removing it again decreases the Tukey depth by at most d, thus there are indeed at least \(\frac{1}{d}\text {TD}(S,q)\) vertex-disjoint simplices containing q. This argument appears in several papers about algorithmic aspects of Tverberg points, see e.g. [12] or [29], Lemma 2.2. Combining these observations, we thus get the following.

Corollary 7

Let \(\varrho \) be a super-additive depth measure. Then for every point set S and query point q in \({\mathbb {R}}^d\) we have

Let us note here that it could be that the factor \(\frac{1}{d}\) in the last inequality could be improved. Indeed, in the plane, we have that \(\text {TvD}=\min \big \{\text {TD}, \lceil \frac{|S|}{3}\rceil \big \}\) [28]. This fails already in dimension 3 [3]. It would be interesting to see how much the factor \(\frac{1}{d}\) can be improved.

From Corollary 7 it follows that for any super-additive depth measure and any point set there is always a point of depth at least \(\frac{|S|}{d+1}\), for example any Tverberg point. On the other hand, there are depth measures which give the standard depth in \({\mathbb {R}}^1\) which are not super-additive, for example convex hull peeling depth or enclosing depth.

Observation 8

Enclosing depth satisfies conditions (i)-(iii), but not the super-additivity condition (iv).

Proof

It follows straight from the definition that enclosing depth satisfies the conditions (i)–(iii). To see that the super-additivity condition is not satisfied, consider the example in Fig. 1. The point q has enclosing depth 1 with respect to both the set of blue points and the set of red points. However, it can be seen that the enclosing depth of q with respect to both the red and the blue points is still 1. \(\square \)

Enclosing depth does not satisfy the super-additivity condition: the point q has enclosing depth 1 with respect to both the blue and the red points, but its enclosing depth with respect to the union of the two sets is still 1

Full size image

In this section we prove the cascade conjecture for super-additive depth measures whose depth regions are compact and convex. In fact, we will prove the cascade conjecture for the case of weighted point sets. This is not only to achieve greater generality, our proof of Lemma 14 relies on the existence of weights, and does not go through without them.

A weighted point set is a finite point set S together with a weight function \(w:S\rightarrow {\mathbb {R}}_{\ge 0}\) which assigns a weight w(p) to each \(p\in S\). We say that a weighted point set \(S'\) is a strict subset of S, denoted by \(S'\subset S\), if the underlying point set of \(S'\) is a strict subset of the underlying point set of S, and \(w'(p)\le w(p)\) for every \(p\in S'\), where \(w'\) is the weight function on \(S'\). In particular, if \(S'\subset S\), there is a point which is in S but not in \(S'\). For two weighted point sets A and B with weight functions \(w_A\) and \(w_B\), respectively, the weight function on their union \(A\cup B\) is defined as the sum of the respective weight functions. That is, we have \(w(p)=w_A(p)\) for \(p\in A\setminus B\), \(w(p)=w_B(p)\) for \(p\in B{\setminus } A\) and \(w(p)=w_A(p)+w_B(p)\) for \(p\in A\cap B\). Further, for a set S of points we define the weight of S as \(w(S):=\sum _{p\in S}w(p)\). Similarly, by a partition of a weighted point set S into parts A and B we mean two weight functions \(w_A\) and \(w_B\), such that \(w(p)=w_A(p)+w_B(p)\) for \(p\in S\), and by a partition into strict subsets A and B, we mean that both weighted point sets A and B must be strict subsets of S, that is, there are points \(p_A,p_B\) in S for which \(w_A(p_A)=0\) and \(w_B(p_B)=0\). The axioms for super-additive depth measures extend to weighted point sets in the following way:

1. (i)

   for all \(S\in S^{{\mathbb {R}}^d}\) and \(q,p\in {\mathbb {R}}^d\) we have \(|\varrho (S,q)-\varrho (S\cup \{p\},q)|\le w(p)\) (sensitivity),

2. (ii)

   for all \(S\in S^{{\mathbb {R}}^d}\) and \(q\in {\mathbb {R}}^d\) we have \(\varrho (S,q)=0\) for \(q\not \in \text {conv}(S)\) (locality),

3. (iii)

   for all \(S\in S^{{\mathbb {R}}^d}\) and \(q\in {\mathbb {R}}^d\) we have \(\varrho (S,q)\ge \min \{w(p):p\in S\}\) for \(q\in \text {conv}(S)\) (non-triviality),

4. (iv)

   for any disjoint subsets \(S_1,S_2\subseteq S\) and \(q\in {\mathbb {R}}^d\) we have \(\varrho (S,q)\ge \varrho (S_1,q)+\varrho (S_2,q)\) (super-additivity).

Clearly, each point set can be considered as a weighted point set by assigning weight 1 to each point. On the other hand, by placing several points at the same location, normalizing and using the fact that \({\mathbb {Q}}\) is dense in \({\mathbb {R}}\), each depth measure defined on point sets can be extended to weighted point sets. Further, we can again define depth regions \(D_{\varrho }^S(\alpha ):=\{q\in {\mathbb {R}}^d\mid \varrho (S,q)\ge \alpha \}\). We denote by \(t_\alpha \) the dimension of \(D_{\varrho }^S(\alpha )\). We will also use a special depth region, called the median region, denoted by \(M_{\varrho }(S)\), which is the deepest non-empty depth region. More formally, let \(\alpha _0\) be the supremum value for which \(D_{\varrho }^S(\alpha _0)\ne \emptyset \). Then \(M_{\varrho }(S):=D_{\varrho }^S(\alpha _0)\).

We now introduce a continuous version of the cascade condition:

Definition 9

Let \(\varrho \) be a depth measure. If for each weighted point set S we have that

we say that \(\varrho \) is cascading.

We say that a depth measure \(\varrho \) is integral if for any unweighted point set and any query point q the depth \(\varrho (S,q)\) is an integer. Note that all the depth measures introduced so far are integral.

Observation 10

Let \(\varrho \) be an integral depth measure and let S be an unweighted point set of size n. Then

Proof

As \(\varrho \) is integral, we have that \(t_\alpha =t_{\lfloor \alpha \rfloor }\). In particular, for every integer i we have

\(\square \)

In the following, we will show that super-additive depth measures whose depth regions are compact and convex are cascading in two steps. First we will show that if we partition a weighted point set into two parts whose median regions intersect and the cascade condition holds for both parts, then the cascade condition holds for the whole set. In a second step, we prove that we can always partition a point set in such a way, further enforcing that none of the parts contains all points, that is, each part is a strict subset. The claim then follows by induction.

Before we do this, let us describe a way to compute \(\int _0^{w(S)}t_\alpha \textrm{d}\alpha \). Consider some depth region \(D_\varrho ^S(\alpha )\) of dimension k and assume without loss of generality that the origin lies in the median region. Being convex, this depth region lies in some k-dimensional linear subspace \(H\subset {\mathbb {R}}^d\). Considering all depth regions, they lie in a sequence of nested linear subspaces, also known as a flag. We can find a basis \(F=\{f_1,\ldots ,f_d\}\) of \({\mathbb {R}}^d\) such that each relevant linear subspace is spanned by a subset of the basis vectors. We call F a basis of S.

For each weighted point set S and each vector v, we define the survival time \(\tau _S(v):=\sup \{\alpha \mid v\in \text {span}(D_\varrho ^S(\alpha ))\}\). Similarly, we define \(\tau _S(0):=\alpha _0\), where as above \(\alpha _0\) is the supremum value for which \(D_{\varrho }^S(\alpha _0)\ne \emptyset \). In other words, we view \(\tau _S(0)\) as the survival time of the origin.

Lemma 11

Let \(F=\{f_1,\ldots ,f_d\}\) be a basis of \({\mathbb {R}}^d\), and write \(f_0:=0\). Then

Further, if F is a basis of S, then we have equality.

Proof

For an illustration of the proof see Fig. 2. Without loss of generality, assume \(\tau _S(f_d)\le \cdots \le \tau _S(f_1)\le \tau _S(f_0)\). Consider some \(\alpha \le \tau _S(f_i)\). The span of \(D_\varrho ^S(\alpha )\) contains all basis vectors \(f_i,f_{i-1},\ldots ,f_1\), thus we have \(t_\alpha \ge i\). We thus get

If F is a basis of S, then for \(\tau _S(f_{i+1})\le \alpha <\tau _S(f_i)\) we have \(t_\alpha = i\) and thus the above inequality is an equality. \(\square \)

\(\int _0^{w(S)}t_\alpha d\alpha \ge \sum _{i=0}^d\tau _S(f_i)-w(S)\)

Full size image

We will also use the following auxiliary lemma, which is well-known, see e.g. [23], Prop. 5.37 for a reference.^{Footnote 2}

Lemma 12

Let A and B be two flags in a d-dimensional vector space V. Then we can find a basis F which is a common basis of both flags.

Lemma 13

Let \(\varrho \) be a super-additive depth measure whose depth regions are convex and let \(S_1\) and \(S_2\) be two weighted point sets in \({\mathbb {R}}^d\) whose median regions intersect. Assume that the cascade condition holds for \(S_1\) and \(S_2\). Then the cascade condition holds for \(S_1\cup S_2\).

Proof

We may assume without loss of generality that the origin is in both median regions. By Lemma 12, we can choose a basis \(F=\{f_1,\ldots ,f_d\}\) of \({\mathbb {R}}^d\) that is a basis of both \(S_1\) and \(S_2\). Again, we write \(f_0=0\).

For \(i\ne 0\), let \(\ell _i\) be the line \(\{\lambda f_i\mid \lambda \in {\mathbb {R}}\}\). Note that by the convexity of the depth regions \(f_i\in \text {span}(D_\varrho ^S(\alpha ))\}\) implies that \(\ell _i\cap D_\varrho ^S(\alpha )\) is an interval with non-empty relative interior. In particular, assuming \(f_i\in \text {span}(D_\varrho ^{S_1}(\alpha _1))\}\) and \(f_i\in \text {span}(D_\varrho ^{S_2}(\alpha _2))\}\), we get two such intervals whose intersection has a non-empty relative interior. Thus, there is a point \(p\ne 0\) on \(\ell _i\) which lies both in \(D_\varrho ^{S_1}(\alpha _1)\) and \(D_\varrho ^{S_2}(\alpha _2)\). By the super-additivity condition, p lies in \(D_\varrho ^{S_1\cup S_2}(\alpha _1+\alpha _2)\). It follows that \(\tau _{S_1\cup S_2}(f_i)\ge \tau _{S_1}(f_i)+\tau _{S_2}(f_i)\) for \(i\ne 0\). The same argument for the origin gives \(\tau _{S_1\cup S_2}(f_0)\ge \tau _{S_1}(f_0)+\tau _{S_2}(f_0)\). Thus, using Lemma 11 we get

\(\square \)

Lemma 14

Let \(\varrho \) be a super-additive depth measure whose depth regions are compact and convex and let S be a weighted point set in \({\mathbb {R}}^d\) with \(|S|\ge d+2\). Then there exists a partition of S into strict subsets \(S_1\) and \(S_2\) whose median regions intersect.

Proof

Consider the barycentric subdivision B of the boundary \(\partial \Delta \) of the simplex with vertices S. There is a natural identification of the vertices of B with strict subsets of S (see Fig. 3). Thus, for any such vertex \(b\in B\) we get a strict weighted subset S(b) with \(w_{S(b)}(p)=w(p)\) if p is in the subset S(b) and \(w_{S(b)}(p)=0\) otherwise. We can extend this assignment linearly to \(\partial \Delta \): for each point b in the relative interior of a simplex \((b_1,\ldots ,b_k)\) of B, consider its barycentric coordinates \((x_1,\ldots ,x_k)\), \(\sum x_i=1\), and define \(w_{S(b)}(p):=\sum x_i\cdot w_{S(b_i)}(p)\) for each \(p\in S\). This defines a continuous map which assigns to each point b on \(\partial \Delta \) a strict weighted subset S(b) of S. Further, under the natural antipodality on \(\partial \Delta \), we get complements of the weighted subsets, that is, \(S(-b)=S(b)^C\).

We claim that for some point b on \(\partial \Delta \) we have that the median regions M(b) and \(M(-b)\) of S(b) and \(S(-b)\) intersect. If this is true, our claim follows by setting \(S_1=S(b)\) and \(S_2=S(-b)\). For a set A, denote by \(-A\) its reflection at the origin. For each b on \(\partial \Delta \), let \(Q(b):=M(b)-M(-b)\) be the Minkowski sum of M(b) and \(-M(-b)\). Note that M(b) and \(M(-b)\) intersect if and only if \(0\in Q(b)\) and that \(Q(-b)=-Q(b)\). Further, as Q(b) is a Minkowski sum of compact convex sets, Q(b) is itself compact and convex.

Consider now the real vector bundle \(\pi : E\rightarrow B\) obtained from attaching \({\mathbb {R}}^d\) to each point of \(\partial \Delta \) and taking the quotient with respect to the antipodality and let z be its zero section. Following [39], we say that \(\phi \) is a multivalued section if for every \(x\in B\) we have that \(\phi (x)\subseteq \pi ^{-1}(x)\). A multivalued section is said to be convex if \(\phi (x)\) is convex for every \(x\in B\). A multivalued section is called compact if \(\Gamma (\phi ):=\{(x,v)\mid v\in \phi (x)\}\) is a compact set in \(B\times E\). It follows from the above arguments that Q is a convex multivalued section. Further, as each Q(b) is compact and \(\partial \Delta \) is compact, Q is also compact. Now, Proposition 1 from [39] states that if \(\pi : E\rightarrow B\) is a real vector bundle over a compact space B which does not admit a nowhere zero section, then for every multivalued convex compact section \(\phi \) there exists a point \(x\in B\) for which \(z(x)\in \phi (x)\). Thus, in order to show that some Q(b) contains the origin, it is sufficient to show that \(\pi : E\rightarrow B\) does not admit a nowhere zero section.

Now, \(\partial \Delta \) is homeomorphic to the sphere \(S^{|S|-2}\), and the antipodality on \(\partial \Delta \) corresponds to the standard antipodality on the sphere. As \(|S|\ge d+2\), the non-existence of a nowhere zero section thus follows from the Borsuk-Ulam theorem. \(\square \)

While we have only shown that there is a partition, Bourgin-Yang-type theorems [7, 38] tell us, that the space of possible partitions has to be large. In particular, it has dimension at least \(|S|-d-2\). Depending on the application, this might be used to enforce other conditions on the partitions.

Vertices of the barycentric subdivision correspond to strict subsets

Full size image

Theorem 15

Let \(\varrho \) be a super-additive depth measure whose depth regions are compact and convex. Then \(\varrho \) is cascading.

Proof

Let S be a weighted point set in \({\mathbb {R}}^d\). We will do a double induction over the dimension d and the number of points |S|. The case \(d=1\) is straight-forward. In the following, let \(d>1\). We may assume that S does not lie in some lower-dimensional affine subspace, otherwise the result follows from induction on the dimension. We want to show that the cascade condition holds for S. We prove this by induction on |S|. If \(|S|< d+1\), then S lies in some lower-dimensional subspace. If \(|S|= d+1\) and S does not lie in some lower-dimensional subspace, then S must be the vertices of a simplex \(\Delta \). By the non-triviality condition (iii), for any point q in a face F of \(\Delta \), we have \(\varrho (S,q)\ge \min \{w(s):s\text { is a vertex of } F\}\). Let \((s_1,\ldots ,s_{d+1})\) be an ordering of the points such that \(w(s_1)\le w(s_2)\le \cdots \le w(s_{d+1})\) and let \(f_i:=s_{d+1}-s_i\) be a basis of \({\mathbb {R}}^d\). As \((s_1,\ldots ,s_k)\) spans a face of \(\Delta \), for each \(k\le d+1\) we have that for \(\alpha \le w(s_k)\) the region \(D_\varrho ^S(\alpha )\) contains the convex hull of the points \((s_k,\ldots , s_{d+1})\). In particular, its dimension is at least \(d+1-k\) and the survival time \(\tau _S(f_k)\) of \(f_k\) is at least \(w(s_k)\). It follows that \(\sum _{i=0}^{d}\tau _S(f_i)\ge w(S)\) and thus by Lemma 11\(\int _0^{w(S)}t_\alpha d\alpha \ge \sum _{i=0}^d\tau _S(f_i)-w(S)\ge 0\).

Now assume that \(|S|\ge d+2\). By Lemma 14, we can partition S into \(S_1\) and \(S_2\) whose median regions intersect. Note that \(|S_1|,|S_2|<|S|\), so by the induction hypothesis the cascade condition holds for both \(S_1\) and \(S_2\). Thus, by Lemma 13, the cascade condition also holds for S. \(\square \)

As noted above, an example of a super-additive depth measure with compact convex depth regions is Tukey depth. Thus, we get the following.

Corollary 16

Tukey depth is cascading.

On the other hand, while Tverberg depth is super-additive, its depth regions are in general not convex; in fact, they are not even connected. A weak version of Kalai’s cascade conjecture claims that the cascade condition holds for the convex hull of Tverberg depth regions. These depth regions are convex by definition, but the resulting depth measure is in general not super-additive anymore. So while our approach proves the cascade conjecture for Tukey depth, solving Kalai’s cascade conjecture even in its weak form likely requires additional ideas. In fact, it is unclear whether there are any super-additive depth measures with convex depth regions that are not just Tukey depth on potentially reweighted points. In general, the closer study of the structure of the family of super-additive depth measures is an interesting open problem. As every super-additive depth measure is bounded from below by Tverberg depth, solving the strong version of Kalai’s cascade conjecture would imply that all super-additive depth measures are cascading. Further, as noted by Kalai for Tverberg depth [15], any cascading depth measure must enforce deep points. More precisely, if \(\varrho \) is a cascading depth measure and S is a point set in \({\mathbb {R}}^d\), then there must be a point \(q\in {\mathbb {R}}^d\) for which \(\varrho (S,q)\ge \frac{|S|}{d+1}\). Indeed, if there was no such point, we would have \(d_{|S|/(d+1)}=-1\), and even if \(d_i=d\) for all \(i<\frac{|S|}{d+1}\), the sum \(\sum _{i=1}^{|S|}d_i\) would still be negative. The existence of deep points is the main feature of the next family of depth measures that we study.

The second family of depth measures we consider are central depth measures. A combinatorial depth measure \(\varrho : (S^{{\mathbb {R}}^d},{\mathbb {R}}^d)\rightarrow {\mathbb {R}}_{\ge 0}\) is called central if it satisfies the following conditions:

1. (i)

   for all \(S\in S^{{\mathbb {R}}^d}\) and \(q,p\in {\mathbb {R}}^d\) we have \(|\varrho (S,q)-\varrho (S\cup \{p\},q)|\le 1\) (sensitivity),

2. (ii)

   for all \(S\in S^{{\mathbb {R}}^d}\) and \(q\in {\mathbb {R}}^d\) we have \(\varrho (S,q)=0\) for \(q\not \in \text {conv}(S)\) (locality),

3. (iii’)

   for every \(S\in S^{{\mathbb {R}}^d}\) there is a \(q\in {\mathbb {R}}^d\) for which \(\varrho (S,q)\ge \frac{1}{d+1} |S|\) (centrality),

4. (iv’)

   for all \(S\in S^{{\mathbb {R}}^d}\) and \(q,p\in {\mathbb {R}}^d\) we have \(\varrho (S\cup \{p\},q)\ge \varrho (S,q)\) (monotonicity).

Note that conditions (i) and (ii) are the same as for super-additive depth measures, so by Observation 5 we have \(\varrho (S,q)\le \text {TD}(S,q)\) for every central depth measure. Further, for integral depth measures, conditions (iii’) and (iv’) imply the non-triviality condition (iii) for super-additive depth measures: by the centrality condition (iii’) and integrality, every point in the relative interior of a simplex spanned by points of S must have depth at least 1, and thus by the monotonicity condition (iv’), every point in the interior of the convex hull of S has depth at least 1, as by Carathéodory’s theorem each point in the convex hull lies in a simplex. On the other hand, the super-additivity condition (iv) is stronger than the monotonicity condition (iv’), so at first glance, the families of super-additive depth measures and central depth measures are not comparable. However, we have seen before that any super-additive depth measure indeed satisfies the centrality condition, so central depth measures are a superset of super-additive depth measures. It is actually a strict superset, as for example the depth measure whose depth regions are defined as the convex hulls of Tverberg depth regions is central but not super-additive.

While central depth measures enforce deep points by definition, they might still differ a lot locally. In the following, we will show that for most query points we can bound by how much they differ locally, showing that every central depth measure is a constant factor approximation of Tukey depth.

We say that a query point q is in general position relative to S if there is no hyperplane containing q and d points of S. Another way to view this is the following: consider again all hyperplanes spanned by d or more points of S and recall that this defines an arrangement A of hyperplanes, whose cells are the connected components of \({\mathbb {R}}^d\setminus A\). Then a query point q is in general position with respect to S if and only if it lies in a cell of A.

Theorem 17

Let \(\varrho \) be a central depth measure in \({\mathbb {R}}^d\), q a point in \({\mathbb {R}}^d\) and S a finite set of points in \({\mathbb {R}}^d\), where q is in general position with respect to S. Then there exists a constant \(c=c(d)\), which depends only on the dimension d, such that

Here the first inequality is just Observation 5. As for the second inequality, we would like to argue that if S k-encloses q then \(\varrho (S,q)\ge k\). By centrality, there must indeed be a point \(q'\) with \(\varrho (S,q')\ge k\) (note that \(|S|=k(d+1)\) by definition of k-enclosing). As \(\varrho \) is bounded from above by Tukey depth, this point has to lie in the centerpoint region, that is, the region \(D_{\text {TD}}^S(|S|/(d+1))\) of points of Tukey depth at least \(|S|/(d+1)\). However, the point can lie anywhere in the centerpoint region of S and not every point in the centerpoint region is k-enclosed by S. We will show that by adding \(d+1\) points very close to q, we can ensure that q is the only possible centerpoint in the new point set, and the second inequality then follows from sensitivity and monotonicity after removing these points again. A formal argument for this follows in Lemma 18.

This argument can be generalized even to a relaxation of central depth measures: We say that a combinatorial depth measure is \(\alpha \)-central if it satisfies conditions (i), (ii) and (iv’), and the following weak version of condition (iii’): for every \(S\in S^{{\mathbb {R}}^d}\) there is a \(q\in {\mathbb {R}}^d\) for which \(\varrho (S,q)\ge \alpha |S|\) (\(\alpha \)-centrality).

Lemma 18

Let \(\alpha >\frac{1}{d+2}\), and let \(\varrho \) be an \(\alpha \)-central depth measure. Let q be a point in \({\mathbb {R}}^d\) and S a finite set of points in \({\mathbb {R}}^d\), where q is in general position with respect to S. Then

In particular, if \(\alpha =\frac{1}{d+1}\), then \(\varrho (S,q)\ge \text {ED}(S,q)-(d+1)\).

Before proving Lemma 18, let us state and prove some facts about enclosing sets that will be helpful in the upcoming proof. For the first fact, recall that the convex hulls of the \(S_i\) are well-separated if for each \(I\subseteq \{1,\ldots ,d+1\}\) the convex hulls of \(\bigcup _{i\in I}S_i\) and \(\bigcup _{i\notin I}S_i\) can be separated by a hyperplane. This is known to be equivalent to saying that there is no hyperplane that intersects all convex hulls of the \(S_i\), see e.g. Chapter 4.2 in [34].

Lemma 19

Let \(S_1,\ldots , S_{d+1}\) be point sets in \({\mathbb {R}}^d\) which enclose a point q, where q is in general position with respect to \(S=S_1\cup \cdots \cup S_{d+1}\). Then the convex hulls of \(S_1,\ldots , S_{d+1}\) are well-separated.

Proof

By the above remark it is enough to show that there is no hyperplane that intersects all the convex hulls \(\text {conv}(S_1),\ldots ,\text {conv}(S_{d+1})\). Assume for the sake of contradiction that there is such a hyperplane H. Assume first that H contains q. By the general position assumption, H can contain at most \(m\le d-1\) points of S. In particular the convex hull of \(S\cap H\) lies in an affine subspace of dimension at most \(m-1\le d-2\). If q lies in the convex hull of \(S\cap H\), then \(S\cap H\) together with any \(d-m\) other points of S spans a hyperplane containing d points of S and q, which is excluded by the general position assumption. Thus, q does not lie in the convex hull of \(S\cap H\). Let now \(H^+\) denote the closed positive side of H. As H intersects all convex hulls, we have \(S_i\cap H^+\ne \emptyset \) for all \(i\in \{1,\ldots ,d+1\}\). For each \(S_i\) pick some point \(s_i\in S_i\). As all of these points are on the same side of H, the point q can only be in the convex hull of the transversal \(s_1,\ldots ,s_{d+1}\) if it is in the convex hull of the points of the transversal lying on H. However, as q is not in the convex hull of \(S\cap H\), we conclude that q is not in the chosen transversal, which is a contradiction to the assumption that \(S=(S_1,\ldots ,S_{d+1})\) encloses q.

Assume now that H does not contain q. Then, analogously, one of the closed sides of H does not contain q but contains a transversal \(s_i\in S_i\) which hence does not contain q in its convex hull, which is a contradiction to the fact that \(S_1,\ldots , S_{d+1}\) encloses q. \(\square \)

Lemma 20

Let \(S_1,\ldots , S_{d+1}\) be point sets in \({\mathbb {R}}^d\) which enclose a point q, where q is in general position with respect to \(S=S_1\cup \cdots \cup S_{d+1}\). Then there are \(d+1\) closed halfspaces \(H_1,\ldots ,H_{d+1}\) such that each \(H_i\) contains q on its boundary, \(H_i\cap S=S_i\) for each i and \(H_1\cup \cdots \cup H_{d+1}={\mathbb {R}}^d\).

Proof

By Lemma 19, the convex hulls of \(S_1,\ldots , S_{d+1}\) are well-separated. Consider the family \(Q_j:=(S_1,\ldots ,S_{j-1},S_{j+1},\ldots ,S_{d+1})\). Clearly, \(Q_j\) is also well-separated: a hyperplane separating the convex hulls of \(\bigcup _{i\in I}S_i\) and \(\bigcup _{i\notin I}S_i\) for \(I\subseteq \{1,\ldots ,d+1\}\) also separates the convex hulls of \(\bigcup _{i\in I{\setminus }\{j\}}S_i\) and \(\bigcup _{i\notin I{\setminus }\{j\}}S_i\). A generalized version of the Ham–Sandwich theorem states that that for d well-separated point sets \(P_1,\ldots ,P_d\) in general position for any \((\alpha _1,\ldots , \alpha _d)\), where \(0\le \alpha _i\le |P_i|\), there is a hyperplane L for whose positive side \(L^+\) we have \(|L^+\cap P_i|=\alpha _i\) for each i [4, 33]. We may further assume that L is tangent to each \(P_i\), that is, L contains a point of each \(P_i\).

Consider now the family \(Q_i\) and choose the orientation of hyperplanes intersecting the convex hulls of \(Q_i\) in such a way that their positive sides contain \(S_i\). By the generalized Ham–Sandwich theorem there is thus a hyperplane \(L_i\) tangent to the sets in \(Q_i\) for which \(S_i\) lies in the positive side \(L_i^+\) and all sets of \(Q_i\) lie on the negative side. We note that q lies in the interior of \(L_i^+\): by the general position assumption, it cannot lie in \(L_i\), and if it were on the negative side, then the tangent points together with any point from \(S_i\) would be a transversal which does not contain q in its convex hull. Further, note that \(L_1^+\cap \cdots \cap L_{d+1}^+\subseteq \text {conv}(S)\) and is thus a bounded convex region, which implies that \(L_1^+\cup \cdots \cup L_{d+1}^+={\mathbb {R}}^d\). The result now follows from translating each \(L_i\) so that it contains q. \(\square \)

For \(S_1,\ldots ,S_{d+1}\) enclosing a point q, we define for each \(S_i\) the cone \(C_i\) with apex q by taking positive combinations of vectors \(\overrightarrow{qs}\) for \(s\in S_i\).

Lemma 21

Let \(S_1,\ldots , S_{d+1}\) be point sets in \({\mathbb {R}}^d\) which enclose a point q, where q is in general position with respect to \(S=S_1\cup \cdots \cup S_{d+1}\). Let p be any point in the cone \(C_i\). Then \(S_1,\ldots ,S_i\cup \{p\},\ldots , S_{d+1}\) also encloses q.

Proof

We claim that there is no halfspace \(H^+\) with q on its boundary which intersects all of \(C_1\setminus \{q\},\ldots ,C_{d+1}\setminus \{q\}\). This follows analogously to Lemma 19: if such a halfspace exists, then it contains a transversal which does not contain q in its convex hull. To show that \(S_1,\ldots ,S_i\cup \{p\},\ldots , S_{d+1}\) encloses q, assume for the sake of contradiction that there is a transversal \(s_j\in S_j\) which does not contain q in its convex hull. As both the convex hull and q are convex and compact, by the separation theorem there exists a hyperplane H separating the two. Translate the separating hyperplane H such that it contains q and orient it in such a way that its positive side \(H^+\) contains the convex hull of the transversal. Then \(H^+\) intersects all of \(C_1\setminus \{q\},\ldots ,C_{d+1}\setminus \{q\}\), which is a contradiction. \(\square \)

We are now ready to prove Lemma 18:

Proof

Let \(\text {ED}(S,q)=k\) and let \(S'=(S'_1,\ldots ,S'_{d+1})\) be a witness subset. Recall that by monotonicity, we have \(\varrho (S,q)\ge \varrho (S',q)\). We first claim that \(\text {TD}(S',q')\le k\) for all \(q'\in {\mathbb {R}}^{d}\): indeed, by Lemma 20, one of the halfspaces \(H_1,\ldots ,H_{d+1}\) contains \(q'\) and exactly one of the \(S'_i\). On the other hand, as any transversal of \(S'_1,\ldots ,S'_{d+1}\) gives a simplex having the point q in its interior, we get that \(\text {TvD}(S',q)=k\), and thus, as \(\text {TD}(S',q)\ge \text {TvD}(S',q)\) and \(\text {TD}(S',q)\le k\) we get that \(\text {TD}(S',q)= k\).

Let \(\alpha ':=(d+1)\alpha \) and let \(m:=\lfloor \frac{1-\alpha '}{\alpha '}k+1\rfloor \). Let Z be the cell of the hyperplane arrangement induced by \(S'\) which contains q and let B be a small enough neighborhood of q such that B lies completely in the interior of Z. For each i add m points in \(C_i\cap B\). By Lemma 21, this new point set P \((k+m)\)-encloses q. The new point set P has \((d+1)(k+m)\) many points, and we have ss

We claim that for any point \(q'\) that is not in Z we still have \(\text {TD}(P,q')\le k\): by Lemma 20, the point \(q'\) lies in one of the halfspaces \(H_1,\ldots ,H_{d+1}\), without loss of generality \(H_1\). Translate \(H_1\) until it does not intersect B anymore. As B was chosen sufficiently small, \(H_1\) still contains \(q'\) and we have \(|P\cap H_1|=|S'_1|=k\) by construction.

Thus, as \(\varrho (P,q')\le \text {TD}(P,q')\), the only points \(q'\) for which \(\varrho (P,q')\ge \alpha |P|\) is possible are by construction in B. As \(B\subset Z\) and all points in Z had the same depth before adding the new points, we can assume that we have \(\varrho (P,q)\ge \alpha |P|\). By sensitivity we now have

Plugging in \(\alpha ':=(d+1)\alpha \) we get

As \((d+2-\frac{1}{\alpha })>0\) for \(\alpha >\frac{1}{d+2}\) and \((d+2-\frac{1}{\alpha })=1 \), for \(\alpha =\frac{1}{d+1}\) the claim follows. \(\square \)

The most involved part of Theorem 17 is the last inequality, which we will prove in the next section.

In this section, we will give a new proof of a lower bound on the enclosing depth in terms of Tukey depth:

Theorem 22

(E(d)) There is a constant \(c_1=c_1(d)\) such that for all \(S\in S^{{\mathbb {R}}^d}\) and \(q\in {\mathbb {R}}^d\) we have \(\text {ED}(S,q)\ge c_1\cdot \text {TD}(S,q)\).

We will denote this statement in dimension d by E(d). Note that E(1) is true and \(c_1(1)=1\).

This theorem has appeared in the literature before, both implicitly and explicitly. First, it could be proved using the semi-algebraic same type lemma due to Fox et al. [11], combined with the first selection lemma (see e.g. [21]). Alternatively, a result by Pach [26] gives a lower bound on a colorful variant of enclosing depth in terms of colorful simplicial depth. As colorful simplicial depth can be bounded from below in terms of simplicial depth, which in turn can be bounded from below in terms of Tukey depth (see e.g. [37]), the result follows. An explicit lower bound on enclosing depth in terms of Tukey depth was given by Fabila-Monroy and Huemer [10].

Here we will give a different proof for two reasons: first, the bounds on \(c_1\) that our proof gives are better than the bounds we get from the other proofs. Second, our proof shows an intimate relation of enclosing depth to the following positive fraction Radon theorem on certain bichromatic point sets, which we believe to be of independent interest.

Let \(P=R\cup B\) be a bichromatic point set with color classes R (red) and B (blue). We say that B surrounds R if for every halfspace h we have \(|B\cap h|\ge |R\cap h|\). Note that this in particular implies \(|B|\ge |R|\). The positive fraction Radon theorem is now the following:

Theorem 23

(R(d)) Let \(P=R\cup B\) be a bichromatic point set where B surrounds R. Then there is a constant \(c_2=c_2(d)\) such that there are integers a and b and pairwise disjoint subsets \(R_1,\ldots ,R_a\subseteq R\) and \(B_1,\ldots ,B_b\subseteq B\) with

1. 1.

   \(a+b=d+2\),

2. 2.

   \(|R_i|\ge c_2\cdot |R|\) for all \(1\le i\le a\),

3. 3.

   \(|B_i|\ge c_2\cdot |R|\) for all \(1\le i\le b\),

4. 4.

   for every transversal \(r_1\in R_1,\ldots ,r_a\in R_a, b_1\in B_1,\ldots , b_b\in B_b\), we have \(\text {conv}(r_1,\ldots ,r_a)\cap \text {conv}(b_1,\ldots ,b_b)\ne \emptyset \).

In other words, the Radon partition respects the color classes. We will denote the above statement in dimension d by R(d).

Lemma 24

R(1) can be satisfied choosing \(a=1\), \(b=2\) and \(c_2(1)=\frac{1}{3}\).

Proof

Consider two points \(x_1\) and \(x_2\) such that there are exactly \(\frac{|R|}{3}\) blue points to the left of \(x_1\) and to the right of \(x_2\), respectively. Define \(B_1\) as the set of blue points left of \(x_1\) and \(B_2\) as the set of blue points right \(x_2\). We then have \(|B_1|=|B_2|=\frac{1}{3}|R|\). Further, as B surrounds R, we have at most \(\frac{|R|}{3}\) red points to the left of \(x_1\), and also to the right of \(x_2\). In particular, there are at least \(\frac{|R|}{3}\) red points between \(x_1\) and \(x_2\). Let now \(R_1\) be any subset of \(\frac{|R|}{3}\) red points between \(x_1\) and \(x_2\). It follows from the construction that \(\text {conv}(R_1)\cap \text {conv}(B_1,B_2)\ne \emptyset \). \(\square \)

In the following, we will prove that \(R(d-1)\Rightarrow E(d)\) and that \(E(d-1)\Rightarrow R(d)\). By induction, these two claims then imply the above theorems.

Lemma 25

\(R(d-1)\Rightarrow E(d)\).

Proof

We assume that q does not coincide with a point from S, otherwise we just remove that point from S. Assume that \(\text {TD}(S,q)=k\) and let h be a witnessing hyperplane, that is, a hyperplane which contains q but no points of S and has exactly k points of S on its positive side. Without loss of generality, assume that q is the origin and that h is the hyperplane through the equator on \(S^{d-1}\subseteq {\mathbb {R}}^d\), with exactly k points below. Color the points below h red and the points above h blue. Now, for every point \(p\in S\), consider the line through p and q and let \(p'\) be the intersection of that line with the tangent hyperplane to the north pole of \(S^{d-1}\). Color \(p'\) the same color as p. This gives a bichromatic point set \(S'=R\cup B\) in \({\mathbb {R}}^{d-1}\). Further, in \(S'\), we have that B surrounds R: Assume there is a hyperplane \(\ell \) (in \({\mathbb {R}}^{d-1}\)) with r red points and b blue points on its positive side, where \(r>b\). In \({\mathbb {R}}^d\), this lifts to a hyperplane containing q with \(k-r\) red points and b blue points on its positive side (note that there are exactly k red points). However, \(k-r+b<k\), whenever \(r>b\), thus we would have \(\text {TD}(S,q)<k\), which is a contradiction.

As we now have a point set in \({\mathbb {R}}^{d-1}\), in which B surrounds R, we can apply \(R(d-1)\) to find families of \(d+2\) subsets of \(S'\), each of size \(c_2\cdot k\), some red and some blue, such that in each transversal the color classes form a Radon partition. We claim that the corresponding subsets of S \((c_2\cdot k)\)-enclose q. Pick some transversal (which we call the original red and blue points) and consider the corresponding subset in \(S'\). Let z be a point in the intersection of the convex hulls of the two color classes, and let g be the line through z and q. As z is in the convex hull of the blue points, there is a point \(z^+\) on g which is in the convex hull of the original blue points, and thus above h. Similarly, there is a point \(z^-\) on g which is in the convex hull of the original red points, and thus below h. As q is in the convex hull of \(z^+\) and \(z^-\), it is thus in the convex hull of the original blue and red points. \(\square \)

In particular, this proof shows that \(c_1(d)\ge c_2(d-1)\).

For the proof of the second implication, we need to recall a few results, starting with the Same Type Lemma by Bárány and Valtr [6].

Theorem 26

(Theorem 2 in [6]) For every two natural numbers d and m there is a constant \(c_3(d,m)>0\) with the following property: Given point sets \(X_1,\ldots ,X_m\subseteq {\mathbb {R}}^d\) such that \(X_1\cup \cdots \cup X_m\) is in general position, there are subsets \(Y_i\subseteq X_i\) with \(|Y_i|\ge c_3\cdot |X_i|\) such that all transversals of the \(Y_i\) have the same order type.

We note that while Theorem 2 in [6] is stated using the general position assumption, in Remark 5 of the same paper it is mentioned that the result still holds without it and, in fact, even holds for Borel measures instead of point sets.

From the proof in [6], we get \(c_3(d,m)=2^{-m^{O(d)}}\). This bound has been improved in [11] to \(c_3(d,m)=2^{-O(d^3m\log m)}\).

The second result that we will need is the Center Transversal Theorem, proved independently by Dol’nikov [9] as well as Zivaljević and Vrećica [39]. We will only need the version for two colors, so we state it in this restricted version:

Theorem 27

(Center Transversal for two colors) Let \(\mu _1\) and \(\mu _2\) be two finite Borel measures on \({\mathbb {R}}^d\). Then there exists a line \(\ell \) such that for every closed halfspace H which contains \(\ell \) and every \(i\in \{1,2\}\) we have \(\mu _i(H)\ge \frac{\mu _i({\mathbb {R}}^d)}{d}\).

Such a line \(\ell \) is called a center transversal. By a standard argument (replacing points with balls of small radius, see e.g. [22]), the same result also holds for two point sets \(P_1, P_2\), where \(\mu _i(H)\) is replaced by \(|P_i\cap H|\). As we will need similar ideas later, we will briefly sketch a proof of the above theorem. Consider some \((d-1)\)-dimensional linear subspace F, i.e., a hyperplane through the origin, and project both measures to it. For each projected measure, consider the centerpoint region (i.e., the region of Tukey depth \(\ge \frac{\mu _i({\mathbb {R}}^d)}{(d-1)+1}\)). This is a non-empty, convex set, so it has a unique center of mass, which we will denote by \(g_i(F)\). Rotating the subspace F in continuous fashion, these centers of mass also move continuously, so the \(g_i(F)\) are two continuous assignments of points to the set of all \((d-1)\)-dimensional linear subspaces. The result then follows from the following Lemma, again proved independently by Dol’nikov ([9], Lemma 1) as well as Zivaljević and Vrećica ([39], Proposition 2). In their works, the result is phrased in terms of sections of the canonical bundle over a the Grassmannian manifold, and follows from more general arguments as we used them in Lemma 14. However, for our current application this weaker statement is sufficient.

Lemma 28

Let \(g_1\) and \(g_2\) be two continuous assignments of points to the set of all \((d-1)\)-dimensional linear subspaces of \({\mathbb {R}}^d\). Then there exists such a subspace F in which \(g_1(F)=g_2(F)\).

Note that in order to apply this Lemma, we had to choose in a continuous way a centerpoint, which we did not need in the similar arguments in Lemma 14. In fact, using Proposition 1 from [39], it would be enough to show that the centerpoint regions form a multivalued compact convex section. The fact that there is a continuous choice of centerpoints is a stronger statement, that might be of independent interest for other applications. If the two measures can be separated by a hyperplane, we can do something similar with the center transversal:

Lemma 29

Let \(\mu _1\) and \(\mu _2\) be two finite Borel measures on \({\mathbb {R}}^d\), which can be separated by a hyperplane. Then there is a canonical choice of a center transversal, that is, a choice of a center transversal which is continuous under continuous changes of the measures.

Proof

Let \(x_1,\ldots ,x_d\) be the basis vectors of \({\mathbb {R}}^d\) and assume without loss of generality that the hyperplane \(H: x_d=0\) separates the two measures \(\mu _1,\mu _2\), with \(\mu _1\) being above H and \(\mu _2\) below. For any \((d-1)\)-dimensional linear subspace F, consider the orthogonal projection \(\pi _F: {\mathbb {R}}^d\rightarrow F\). Note that if F is orthogonal to H, then \(\pi _F(H)\) separates \(\pi _F(\mu _1)\) and \(\pi _F(\mu _2)\), so there is no center transversal parallel to H. It thus suffices to consider only (oriented) subspaces which point upwards (in the sense that the \(x_d\)-component in their normal vector is \(>0\)). The space of these subspaces is homeomorphic to the upper hemisphere \(S^+\) of \(S^{d-1}\).

For each such subspace F let \(G_i(F)\) denote the centerpoint region of the projected mass \(\pi _F(\mu _i)\) and let \(C\subseteq S^+\) be the subset of F where \(G_1(F)\) and \(G_2(F)\) intersect. From the center transversal theorem, we know that C is not empty. Also note that C is independent of the choice of H. We claim that C is a convex subset of \(S^+\).

Consider two subspaces \(F_1\) and \(F_2\) with \(G_1(F_1)\cap G_2(F_1)\ne \emptyset \) and \(G_1(F_2)\cap G_2(F_2)\ne \emptyset \). The shortest path between \(F_1\) and \(F_2\) corresponds to a rotation around a \((d-2)\)-dimensional axis. Let \(F_3\) be a subspace along this rotation, and assume for the sake of contradiction that \(G_1(F_3)\cap G_2(F_3)=\emptyset \). This means that there is a hyperplane \(\ell \) in \(F_3\) separating the two centerpoint regions \(G_1(F_3)\) and \(G_2(F_3)\). In particular, by the definition of the centerpoint regions, \(\ell \) has less than a \(\frac{1}{d}\)-fraction of \(\pi _{F_3}(\mu _1)\) on its positive side, and less than a \(\frac{1}{d}\)-fraction of \(\pi _{F_3}(\mu _2)\) on its negative side, or vice versa. Assume without loss of generality that \(\ell \) goes through the origin. Consider a point in the support of one of the measures. During the rotation of \(F_3\) the projection of this point moves along a line in the projection. In fact, all points move along parallel lines, and the points in the support of \(\mu _1\) move in the opposite direction of the points in the support of \(\mu _2\) and each point crosses a fixed hyperplane through the origin in the projection at most once. Thus, without loss of generality, the fraction of \(\pi _F(\mu _1)\) on the positive side of \(\ell \) only decreases during the rotation from \(F_1\) to \(F_2\), and the same holds for the fraction of \(\pi _F(\mu _2)\) on the negative side of \(\ell \). But then, \(\ell \) still separates \(G_1(F_2)\) and \(G_2(F_2)\) in \(F_2\), and thus \(F_2\notin C\), which is a contradiction. This shows that C is indeed a convex subset of \(S^+\).

Let now F be the center of mass of C. In F, we have that \(G:=G_1(F)\cap G_2(F)\) is a non-empty convex set. Let g be the center of mass of G. As all the above maps are continuous, the preimage \(\pi _F^{-1}(g)\) is now a canonical center transversal.

\(\square \)

Again, the same statement holds for point sets. With these tools at hand, we are now ready to prove the second part of the induction.

Lemma 30

\(E(d-1)\Rightarrow R(d)\).

Proof

Let \(P=R\cup B\) be a bichromatic point set where B surrounds R. Recall that we want to find pairwise disjoint subsets \(R_1,\ldots ,R_a\subseteq R\) and \(B_1,\ldots ,B_b\subseteq B\) with \(a+b=d+2\), all of which contain at least \(c_2\cdot |R|\) points and with the property that for every transversal \(r_1\in R_1,\ldots ,r_a\in R_a, b_1\in B_1,\ldots , b_b\in B_b\), we have \(\text {conv}(r_1,\ldots ,r_a)\cap \text {conv}(b_1,\ldots ,b_b)\ne \emptyset \).

Let \(\ell \) be a line through the origin. Sweep a hyperplane orthogonal to \(\ell \) from one side to the other (without loss of generality from left to right). Let \(h_1\) be a sweep hyperplane with exactly \(\frac{|R|}{3}\) blue points to the left, and let \(A_1\) be the set of these blue points. Similarly, let \(A_2\) be a set of exactly \(\frac{|R|}{3}\) blue points to the right of a sweep hyperplane \(h_2\). Let c be the canonical center transversal of \(A_1\) and \(A_2\) given by Lemma 29 and let g be the \((d-1)\)-dimensional linear subspace which is orthogonal to c. Note that it follows from the proof of Lemma 29 that g cannot be orthogonal to the sweep hyperplanes. We denote the projection of c to g as \(c_A\). Note that \(c_A\) is a centerpoint of the projections of \(A_1\) and of \(A_2\) to g. Now, consider the set M of all red points between \(h_1\) and \(h_2\) and note that as the blue points surround the red points we have \(|M|\ge \frac{|R|}{3}\). Project M to g and denote by \(c_M\) the center of mass of the centerpoint region of the projected point set. We claim that there exists a choice of a line \(\ell \), such that \(c_M=c_A\). As g is not orthogonal to a sweep hyperplane, there is a unique shortest rotation which rotates g to a hyperplane orthogonal to \(\ell \). In particular, these rotations give a homeomorphism from the space of hyperplanes g to the space of hyperplanes orthogonal to the \(\ell \)’s, which is the space of all \((d-1)\)-dimensional linear subspaces. Further, as rotations and projections are continuous and c is a canonical center transversal, \(c_A\) and \(c_M\) are continuous assignments of points, thus the above claim follows from Lemma 28.

So assume now that \(c_M=c_A\). In particular, c is a center transversal for \(A_1\), \(A_2\) and M. Project \(A_1\) to g. The projection of c is a centerpoint of the projection of \(A_1\) in g and g has dimension \(d-1\), thus by the statement \(E(d-1)\) there are three subsets \(A_{1,1}, \ldots A_{1,d}\) of \(A_1\), each of size \(c_1\cdot |A_1|\) whose projections enclose the projection of c. The analogous arguments gives subsets \(A_{2,1}, \ldots , A_{2,d}\) of \(A_2\) and \(M_1,\ldots ,M_d\) of M. Consider now these 3d subsets. By Theorem 26 there are subsets \(A'_{1,1},\ldots ,M'_d\), each of size linear in the size of the original subset, such that each transversal of the subsets has the same order type. Consider such a transversal. By construction, the d points of \(A_1\) contain in their convex hull a point on c which is to the left of \(h_1\). Similarly, the d points of \(A_2\) contain in their convex hull a point on c to the right of \(h_2\). Finally, the d points of M contain in their convex hull a point on c between \(h_1\) and \(h_2\). Thus, the convex hulls of the blue points (from \(A_1\) and \(A_2\)) and the red points (from M) intersect. In particular, by Kirchberger’s theorem [18], there is a subset of \(d+2\) red and blue points, which form a Radon partition where the convex hull of the red points intersects the convex hull of the blue points. Now, choose the subsets from which these points were selected. As every transversal of these subsets has the same order type, every transversal gives a Radon partition which respects the color classes, thus these subsets satisfy the required properties. \(\square \)

This proof shows that \(c_2(d)\ge \frac{c_3(d,3d)}{3}c_1(d-1)\). Using the bound on \(c_3\) from [11] and \(c_1(d)\ge c_2(d-1)\), we thus get \(c_2(d)=\Omega (\frac{c_2(d-2)}{3\cdot 2^{d^4\log d}})=\cdots =\Omega (\frac{1}{3^{d/2}\cdot 2^{d^5\log d}})\), and as \(c_1(d)\ge c_2(d-1)\) we get the same asymptotics for \(c_1\). For comparison, for the constant \(c'\) proven by Fabila-Monroy and Huemer, it follows from their proof that \(c'(d)\ge \frac{c_3(d,2d)}{2}c'(d-1)\), which gives \(c'(d)\in \Omega (\frac{1}{2^{d}\cdot 2^{d^5\log d}})\). It is an interesting open problem, how far these constants can be improved. To the authors knowledge, there are no non-trivial bounds known in the other direction.

Combining this with the results from Sect. 4, we get that any central depth measure is an approximation of Tukey depth. In fact, by Lemma 18 this even holds for many \(\alpha \)-central depth measures.

Corollary 31

Let \(\varrho \) be an \(\alpha \)-central depth measure on \({\mathbb {R}}^d\) where \(\alpha >\frac{1}{d+2}\). Then there exists a constant \(c=c(d)\) such that for every point set S and query point q in \({\mathbb {R}}^d\) we have

We have introduced two families of depth measures, called super-additive depth measures and central depth measures, where the first is a strict subset of the second. We have shown that all these depth measures are a constant-factor approximation of Tukey depth.

It is known that Tukey depth is coNP-hard to compute when both |S| and d is part of the input [14], and it is even hard to approximate [2] (see also [8]). Our result is thus an indication that central depth measures are hard to compute. However, this does not follow directly, as our constant has a doubly exponential dependence on d. It is an interesting open problem whether the approximation factor can be improved.

Further, we have introduced a new depth measure called enclosing depth, which is neither super-additive nor central, but still is a constant-factor approximation of Tukey depth. As it turns out, this depth measure is intimately related to a constant fraction Radon theorem on bi-colored point sets. Finally, we have shown that any super-additive depth measure whose depth regions are convex is cascading.

This last result is motivated by Kalai’s cascade conjecture, which, in the terminology of this paper, states that Tverberg depth is cascading. While this conjecture remains open, we hope that our results might be useful for an eventual proof.

There is a depth measure which has attracted a lot of research, which does not fit into our framework: simplicial depth (\(\text {SD}\)). The reason for this is that while the depths studied in this paper are linear in the size of the point set, simplicial depth has values of size \(O(|S|^{d+1})\). However, after the right normalization, simplicial depth can be reformulated to satisfy all conditions except super-additivity and centrality. It would be interesting to see whether there is some function g depending on point sets and query points such that the depth measure \(\frac{\text {SD}(S,q)}{g(S,q)}\) is super-additive. Such a function, if it exists, could potentially be used to improve bounds for the first selection lemma (see e.g. [21]).