Ham-sandwich cuts and center transversals in subspaces

DOI10.1007/S00454-020-00196-XMaRDI QIDQ2223619zbMATH OpenOpenAlexFDO

Authors Patrick Schnider

Publication date 29 January 2021

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.12516, https://drops.dagstuhl.de/opus/volltexte/2019/10460/

zbMATH Keywords

center transversal theoremham-sandwich theoremmass partitionstopological methods

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Helly-type theorems and geometric transversal theory (52A35) Fixed-point and coincidence theorems (topological aspects) (54H25) Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15)

Abstract: The Ham-Sandwich theorem is a well-known result in geometry. It states that any $d$ mass distributions in $mathbb{R}^d$ can be simultaneously bisected by a hyperplane. The result is tight, that is, there are examples of $d+1$ mass distributions that cannot be simultaneously bisected by a single hyperplane. In this abstract we will study the following question: given a continuous assignment of mass distributions to certain subsets of $mathbb{R}^d$, is there a subset on which we can bisect more masses than what is guaranteed by the Ham-Sandwich theorem? We investigate two types of subsets. The first type are linear subspaces of $mathbb{R}^d$, i.e., $k$-dimensional flats containing the origin. We show that for any continuous assignment of $d$ mass distributions to the $k$-dimensional linear subspaces of $mathbb{R}^d$, there is always a subspace on which we can simultaneously bisect the images of all $d$ assignments. We extend this result to center transversals, a generalization of Ham-Sandwich cuts. As for Ham-Sandwich cuts, we further show that for $d-k+2$ masses, we can choose $k-1$ of the vectors defining the $k$-dimensional subspace in which the solution lies. The second type of subsets we consider are subsets that are determined by families of $n$ hyperplanes in $mathbb{R}^d$. Also in this case, we find a Ham-Sandwich-type result. In an attempt to solve a conjecture by Langerman about bisections with several cuts, we show that our underlying topological result can be used to prove this conjecture in a relaxed setting.

Recommendations

• Orthogonal ham-sandwich theorem in \(\mathbb{R}^3\)
• Generalized ham-sandwich cuts
• Algorithms for ham-sandwich cuts
• Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
• On generalized ``ham sandwich theorems.

Cites work

• A course in topological combinatorics
• A Moment Problem in L 1 Approximation
• A Theorem on General Measure
• An Extension of the Ham Sandwich Theorem
• An improvement on the Rado bound for the centerline depth
• Balanced partitions of 3-colored geometric sets in the plane
• Borsuk-Ulam type theorems on product spaces. II
• Characteristic Classes. (AM-76)
• Equipartition of mass distributions by hyperplanes
• Generalized sandwich theorems
• scientific article; zbMATH DE number 1049272 (Why is no real title available?)
• Measure partitions using hyperplanes with fixed directions
• Mod two homology and cohomology
• Stabbing simplices by points and flats
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• Topology of the Grünbaum–Hadwiger–Ramos hyperplane mass partition problem
• User's guide to equivariant methods in combinatorics. II
• 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

Cited in

(12)

• Bisecting three classes of lines
• Balanced convex partitions of lines in the plane
• Ham Sandwich is equivalent to Borsuk-Ulam
• A survey of mass partitions
• Ham-Sandwich Cuts and Center Transversals in Subspaces
• scientific article; zbMATH DE number 7662165 (Why is no real title available?)
• The topology of projective codes and the distribution of zeros of odd maps
• Transversal generalizations of hyperplane equipartitions
• Bisections of mass assignments using flags of affine spaces
• Cookie cutters: bisections with fixed shapes
• Many partitions of mass assignments
• Complex analogues of the Tverberg-Vrećica conjecture and central transversal theorems

This page was built for publication: Ham-sandwich cuts and center transversals in subspaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223619)