Generalized ham-sandwich cuts (Q603848)

The authors study a discrete version of the well-known ``ham-sandwich problem'' on slicing of convex sets, see for example \textit{I. Bárány, A. Hubard} and \textit{J. Jerónimo} [Twentieth anniversary volume: Discrete and computational geometry. New York, NY: Springer. 65--73 (2009; Zbl 1184.52003)]. One of the main results of the paper under review asserts that if \(P_1, \dots , P_d\) are well-separated point sets in \(\mathbb{R}^d\), and \(a_1, \dots , a_d\) are positive integers such that \(a_i \leq | P_i |\), then {\parindent7mm \begin{itemize}\item[(i)] if there exists a hyperplane \(h \subset \mathbb{R}^d\) for which \(h \cap P_i \neq \emptyset\) and \( | h^+ \cap P_i | = a_i \), for \( 1 \leq a_i \leq d \) (the authors call it \((a_1, \dots , a_d) \)-cut), then this cut is unique; \item[(ii)] if the points of the sets \( P_1, \dots , P_d \) are in a weak general position then such a cut does exist for every \( (a_1, \dots , a_d) \). Here \( a_i \leq | P_i | \), as above. \end{itemize}} The authors propose an algorithm of construction of such a discrete ham-sandwich cut in the case when \( n \) points in a weak general position in \(\mathbb{R}^d\) compose \( d \) well-separated sets. For \( d = 2\) the algorithm finds this cut in a linear time. An estimate \( O(n(\log n)^{d-3}) \) of its running time is obtained for \( d \geq 3 \).