New bounds for the same-type lemma (Q6574401)

Sets \(Y_1,\dots, Y_{d+1}\subset \mathbb{R}^d\) are said to have the \textit{same-type property} if, for every choice of points \(y_1 \in Y_1,\dots, y_{d+1} \in Y_{d+1}\), the orientation of the points \(y_1,\dots, y_{d+1}\) is the same. More generally, the sets \(Y_1,\dots, Y_m \) are said to have the same-type property if every \(d + 1\) of them do. A natural question is the following: given disjoint finite sets \(X_1,\dots ,X_m \subset \mathbb{R}^d\) such that their union is in general position, are there large subsets \(Y_i \subseteq X_i\) such that the sets \(Y_1,\dots, Y_m\) have the same-type property? The same-type lemma proved by \textit{I. Bárány} and \textit{P. Valtr} [Discrete Comput. Geom. 19, No. 3, 335--342 (1998; Zbl 0914.52007)] states that each \(Y_i\) may be taken to have a positive fraction of points from the corresponding \(X_i\). How large could this fraction be? Formally, for disjoint sets \(X_1,\dots ,X_m \subset \mathbb{R}^d\), whose union is in general position, let us denote by \(c(X_1, \dots ,X_m)\) the largest constant \(c\) for which there exist \(Y_1,\dots, Y_m\) having the same-type property and satisfying \(Y_i \subseteq X_i\), \(|Y_i| \geq c|X_i|\). For any fixed number \(m\) and dimension \(d\), denote by \(c(m, d)\) the infimum of \(c\) for all such configurations. The paper under review shows that for \(d\geq 2\) and \(m\geq d\), the constant \(c(m,d)\) depends polynomially from \(m\), if \(d\) is fixed, by showing the bounds \(d^{-50d^3}m^{-d^2}\leq c(m,d)\leq d^dm^{-d}\). In the past, polynomial bounds were known only in the case of equal sized \(X_i\) sets.\N\NAs the same type lemma is frequently used in discrete geometry, this extension is very relevant. A construction is given to show that polynomial dependence on \(m\) is unavoidable. An algorithm is presented to approximate \(c(m, d)\) within a prescribed error.