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 \).
- Algorithms for ham-sandwich cuts
- Computing generalized ham-sandwich cuts
- Weighted Ham-Sandwich Cuts
- Equitable subdivisions within polygonal regions
- Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
- Orthogonal ham-sandwich theorem in \(\mathbb{R}^3\)
- Generalizing ham sandwich cuts to equitable subdivisions
- Few cuts meet many point sets
- Computing balanced convex partitions of lines
- scientific article; zbMATH DE number 4090793
- k-sets in four dimensions
- A positive fraction Erdős-Szekeres theorem
- Algorithms for ham-sandwich cuts
- An improved bound for \(k\)-sets in three dimensions
- Equipartitions of measures by 2-fans
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 1528185 (Why is no real title available?)
- Improved bounds for planar k-sets and related problems
- Partitioning with two lines in the plane
- Simultaneous partitions of measures by \(k\)-fans
- Slicing convex sets and measures by a hyperplane
- Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
- Supporting spheres for families of independent convex sets
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
- Dynamic ham-sandwich cuts in the plane
- Algorithms for ham-sandwich cuts
- Generalizing ham sandwich cuts to equitable subdivisions
- On separating points by lines
- No-dimensional Tverberg theorems and algorithms
- Bisecting envelopes of convex polygons
- Ham-sandwich cuts and center transversals in subspaces
- A superlinear lower bound on the number of 5-holes
- Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
- Few cuts meet many point sets
- Computing generalized ham-sandwich cuts
- A survey of mass partitions
- Ham-Sandwich Cuts and Center Transversals in Subspaces
- Stabbing simplices of point sets with \(k\)-flats
- Geodesic ham-sandwich cuts
- Orthogonal ham-sandwich theorem in \(\mathbb{R}^3\)
- Weighted Ham-Sandwich Cuts
- scientific article; zbMATH DE number 7662165 (Why is no real title available?)
- A stronger conclusion to the classical ham sandwich theorem
- Computational complexity of the -Ham-Sandwich problem
- Two choices are enough for P-LCPs, USOs, and colorful tangents
- An FPT algorithm for splitting a necklace among two thieves
- An FPT algorithm for splitting a necklace among two thieves
- Unfairly splitting separable necklaces
- Uneven splitting of ham sandwiches
This page was built for publication: Generalized ham-sandwich cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q603848)
