Fact-checked by Grok 2 weeks ago

Ham sandwich theorem

The ham sandwich theorem is a fundamental result in geometric topology and measure theory, stating that given any three bounded measurable sets in three-dimensional Euclidean space, there exists a single plane that simultaneously bisects each set, dividing it into two subsets of equal Lebesgue measure.^[1] This theorem generalizes to n dimensions, where n such sets in R^n can always be simultaneously bisected by a single (n-1)-dimensional hyperplane.^[2] The theorem was first conjectured by the Polish mathematician Hugo Steinhaus in the 1930s as part of problems discussed in the Scottish Café mathematical tradition.^[3] Stefan Banach provided the initial proof in 1938, reducing the problem to the Borsuk–Ulam theorem via a continuous function on the sphere that maps directions and offsets of the bisecting plane.^[3] An independent proof for the general n-dimensional case, using differential topology and the concept of index theory for vector fields, was later given by Arthur H. Stone and John W. Tukey in their 1942 paper "Generalized "sandwich" theorems." Beyond its intuitive appeal—often illustrated by the ability to cut a ham sandwich so that the ham, bread, and other fillings are equally divided on each side—the theorem has significant implications in combinatorial geometry and topology.^[2] It serves as a key tool in proving other results, such as the existence of equitable divisions in voting theory or the structure of Kakeya sets in higher dimensions.^[4]^[2] Generalizations include the polynomial ham sandwich theorem by Mikhail Gromov, which allows a degree-d hypersurface to bisect up to \binom{n+d}{d}-1 sets in R^n, extending the theorem's partitioning power.^[2]

Statement

Formal Statement

The ham sandwich theorem states that, in \mathbb{R}^d, for any d bounded, non-negative Borel measures \mu_1, \dots, \mu_d with finite total mass, there exists a hyperplane that simultaneously bisects each measure.^[5] Specifically, there is a hyperplane H dividing \mathbb{R}^d into two open half-spaces H^+ and H^- such that \mu_i(H^+) = \mu_i(H^-) = \frac{1}{2} \mu_i(\mathbb{R}^d) for each i = 1, \dots, d.^[5] This holds more generally for any finite non-negative measures on \mathbb{R}^d, without requiring absolute continuity with respect to Lebesgue measure.^[6] An equivalent formulation applies to compact sets: given d compact subsets K_1, \dots, K_d of \mathbb{R}^d, there exists a hyperplane H such that the Lebesgue measure of each K_i \cap H^+ equals that of K_i \cap H^-.^[5] For probability measures (normalized so \mu_i(\mathbb{R}^d) = 1), the condition simplifies to \mu_i(H^+) = \mu_i(H^-) = \frac{1}{2}.^[6] A discrete version states that, for any d finite sets of points P_1, \dots, P_d in \mathbb{R}^d, there exists a hyperplane H such that each open half-space contains at most half the points from each P_i (with points on H assigned appropriately if the cardinalities are odd). The orientation of the hyperplane can be parameterized by its unit normal vector u \in S^{d-1}, the unit sphere in \mathbb{R}^d, with the offset determined to achieve the bisection.^[5]

Low-Dimensional Illustrations

In two dimensions, the ham sandwich theorem guarantees that given any two bounded measurable sets in the Euclidean plane, there exists a straight line that simultaneously bisects both, dividing each set into two subsets of equal Lebesgue measure.^[7] This bisecting line ensures that half the area (or "mass," assuming uniform density) of each set lies on one side and half on the other, regardless of the sets' shapes, sizes, or relative positions—even if they overlap or are disjoint.^[7] To illustrate, consider two irregular regions on a flat surface, such as a round piece of bread and an amorphous blob of cheese scattered nearby. A single straight-line cut, like the edge of a knife, will divide the bread's area in half while also halving the cheese's area, no matter how convoluted or asymmetrically placed the shapes are.^[8] For a discrete analog, imagine two collections of points (e.g., red dots representing one set and blue dots the other); the theorem assures a line that places approximately half the red points and half the blue points on each open half-plane, treating the points as having equal mass.^[9] Such a configuration can be visualized with the bisecting line threading through the plane, balancing the measures on either side, as depicted in simple diagrams where colored regions or points are symmetrically split by the line. Extending to three dimensions, the theorem states that for any three bounded measurable sets in Euclidean space, there exists a single plane that bisects all three, with each set divided into two parts of equal volume.^[7] Here, the plane acts analogously to the line in 2D, ensuring half the volume (or mass, under uniform density) of each set occupies the space on one side and half on the other, irrespective of the sets' irregular geometries or orientations.^[7] A concrete example involves three solid objects, like two slices of bread and a layer of ham floating freely in a room; a flat plane—envisioned as an infinitesimally thin sheet or the blade of a giant cleaver—can slice through the space to halve the volume of the bread, ham, and the other bread simultaneously, even if the pieces are twisted, overlapping, or positioned arbitrarily.^[8] Visually, this might be represented by three lumpy, non-convex volumes in 3D space, with the bisecting plane intersecting them such that the portions on the positive and negative half-spaces are equal in measure for each. These low-dimensional cases exemplify the general n-dimensional ham sandwich theorem, where n hyperplane bisects n sets.^[7]

Intuition

Geometric Interpretation

The ham sandwich theorem guarantees the existence of a hyperplane that simultaneously bisects n bounded measurable sets in n-dimensional Euclidean space into regions of equal Lebesgue measure, relying on topological principles that ensure such a "balanced cut" must occur. This assurance stems from the continuity of the measure functions associated with half-spaces defined by hyperplanes and the compactness of an appropriate parameter space for these hyperplanes. Specifically, consider a continuous function that maps each possible oriented affine hyperplane to the vector of signed measures (differences between the measures on the two sides, normalized to total measure) of the sets in one half-space; using a compact parameterization of hyperplanes via the n-sphere S^n, the resulting imbalance function is antipodal, and by the Borsuk–Ulam theorem, it must vanish at some point, balancing all measures.^[10]^[2] Oriented affine hyperplanes in \mathbb{R}^n can be compactly parameterized by points on the n-sphere S^n, via homogenization: identify \mathbb{R}^n with the hyperplane \{x_{n+1}=1\} in \mathbb{R}^{n+1}, so each point u \in S^n defines a linear hyperplane \{x \in \mathbb{R}^{n+1} \mid u \cdot x = 0\} in \mathbb{R}^{n+1}, intersecting \{x_{n+1}=1\} in an affine hyperplane in \mathbb{R}^n; antipodal points u and -u define opposite orientations. This parameterization allows continuous variation over the compact sphere S^n, leading to a fixed-point argument (via Borsuk–Ulam) that identifies the balancing configuration. The continuity of the resulting measure imbalance function f: S^n \to \mathbb{R}^n, where each component tracks the normalized difference for one set, is ensured by properties of the Lebesgue measure under continuous deformations of half-spaces.^[10]^[2] The theorem exhibits invariance under affine transformations of \mathbb{R}^n, as such transformations preserve the ratios of measures on either side of the transformed hyperplane, since both half-spaces scale uniformly by the absolute value of the determinant of the linear part. This geometric robustness holds regardless of rigid motions, scalings, or shears, emphasizing the theorem's reliance on the intrinsic topology of the space rather than specific coordinates. Furthermore, the result connects directly to the broader concept of equipartition, where the hyperplane divides the ambient space into two complementary half-spaces without overlaps, each containing exactly half the measure of every set, thus providing a canonical way to partition multiple measures simultaneously.^[10]^[2]

Analogies to Other Theorems

The ham sandwich theorem shares a conceptual similarity with the intermediate value theorem, which guarantees that a continuous function on a closed interval attains every value between its endpoints. In the two-dimensional case of the ham sandwich theorem, known as the pancake theorem, the proof relies on considering directions parameterized by an angle θ from 0 to π and, for each direction, identifying the unique line perpendicular to that direction that bisects the first set; the signed area difference for the second set then defines a continuous function on the circle (with period π and antipodal properties), guaranteeing a direction where the difference is zero by topological arguments akin to the intermediate value theorem.^[1]^[11] The theorem is closely related to the Brouwer fixed-point theorem, which asserts that any continuous function from a closed ball to itself has a fixed point, as both arise from fundamental topological properties ensuring the existence of balanced configurations in continuous settings. Specifically, proofs of the ham sandwich theorem often invoke the Borsuk–Ulam theorem—a consequence of Brouwer's result stating that no continuous antipodal map exists from the n-sphere to R^n—as a key tool to guarantee a hyperplane where all measures are halved simultaneously.^[12] In contrast to the unsolved pancake problem, which seeks the minimal number of prefix reversals (flips) needed to sort a stack of pancakes of varying sizes in the worst case and remains open with known bounds of (15/14)n to (18/11)n flips for large n, the ham sandwich theorem provides a complete existential resolution for simultaneous bisections without requiring optimization over sequences of operations.^[13] The ham sandwich theorem can be viewed as a specific instance of equipartition theorems, which concern dividing a measure into equal parts using geometric objects; while general equipartition results may require multiple hyperplanes or other partitions to achieve equal shares for a single measure, the ham sandwich theorem uniquely accomplishes simultaneous equipartition of n measures using exactly one hyperplane in n dimensions.^[14]

History

Early Discoveries

The origins of the ham sandwich theorem trace back to early 20th-century explorations in geometric measure theory and equipartition problems. Related ideas appeared in earlier work on dividing sets or measures equally, such as simple cases in lower dimensions where a line bisects two areas simultaneously, though these were considered trivial and not formally stated as a theorem. These concepts laid informal groundwork for more complex simultaneous bisections, influencing later formulations without direct attribution to specific mathematicians prior to the 1930s.^[15] In the 1930s, Hugo Steinhaus informally posed the problem in three dimensions during discussions among the Lwów school of mathematicians, asking whether a single plane could bisect three bounded sets—analogous to ham, bread, and cheese—in Euclidean 3-space simultaneously, as recorded in the Scottish Book (problem 123). This conjecture emerged from Steinhaus's interest in intuitive geometric divisions and was later documented in his recollections and the Scottish Book, a collection of problems from the Scottish Café in Lwów spanning the 1930s. Steinhaus's informal statement highlighted the theorem's appealing simplicity while challenging the existence of such a cutting plane for arbitrary compact sets.^[16] A rigorous proof for the 3D case was provided by Stefan Banach and published in 1938 in a note by Steinhaus in Mathesis Polska, using the Borsuk–Ulam theorem to construct a continuous function on the sphere whose zero guarantees the bisecting plane. This proof demonstrated the theorem's validity for Lebesgue measurable sets and marked a seminal application of analytic methods to topological partitioning problems.^[3] An independent generalization to n dimensions for measures, including finite point sets, was provided by Arthur H. Stone and John W. Tukey in their 1942 paper "Generalized 'Sandwich' Theorems" in the Duke Mathematical Journal, using differential topology and index theory for vector fields. This work underscored the theorem's robustness across continuous and discrete settings.^[15]

Naming and Popularization

The term "ham sandwich theorem" originated in the 1940s when John Tukey, during discussions with colleagues at Princeton University, adopted the metaphor for the three-dimensional case, likening the simultaneous bisection of a piece of ham and two slices of bread to a single planar cut. This vivid imagery, inspired by earlier formulations, helped convey the theorem's intuitive appeal in topological partitioning problems.^[3] The theorem gained widespread recognition through Martin Gardner's "Mathematical Games" column in Scientific American, particularly in the late 1950s and early 1960s, where he explored its generalizations and recreational implications. These discussions were compiled in Gardner's 1961 book The Second Scientific American Book of Mathematical Puzzles and Diversions, introducing the concept to non-specialists and sparking interest beyond academic circles.^[17] In mathematical culture, the theorem has become a staple for illustrating topological ideas in education, often featured in introductory courses on geometry and measure theory to demonstrate the power of continuous functions in partitioning spaces.^[15] Its playful analogy has also permeated recreational mathematics, appearing in puzzles that challenge readers to visualize multidimensional cuts and bisecting irregular shapes. Alternative designations include the "sandwich theorem," reflecting its general partitioning nature, and the "Steinhaus–Banach–Tukey theorem," honoring key contributors Hugo Steinhaus, Stefan Banach, and the later work of Tukey with Arthur Stone.^[3]

Proofs

Two-Dimensional Proof

Consider two finite Borel probability measures \mu_1 and \mu_2 on \mathbb{R}^2 with compact support. A line in the plane is parameterized by an angle \theta \in [0, \pi) specifying the direction of its normal vector (\cos \theta, \sin \theta) and a signed distance p \in \mathbb{R} from the origin, given by the equation x \cos \theta + y \sin \theta = p. The associated closed half-plane is H^+(\theta, p) = \{(x, y) \in \mathbb{R}^2 \mid x \cos \theta + y \sin \theta \leq p\}.^[1] For fixed \theta, define g_i(\theta, p) = \mu_i(H^+(\theta, p)) for i = 1, 2. Each g_i(\theta, \cdot) is continuous and nondecreasing in p, with \lim_{p \to -\infty} g_i(\theta, p) = 0 and \lim_{p \to \infty} g_i(\theta, p) = 1 due to compact support. Thus, there exists p = p(\theta) such that g_1(\theta, p(\theta)) = 1/2, and p(\theta) can be chosen continuously in \theta.^[1] Now define the continuous function f: [0, \pi] \to \mathbb{R} by

f(\theta) = g_2(\theta, p(\theta)) - \frac{1}{2}.

The compact support ensures the continuity of f. To see that a zero exists, observe that the parameterization identifies \theta and \theta + \pi up to orientation reversal of the normal vector. Specifically, f(\pi) = -f(0), because the half-plane H^+(\pi, p(\pi)) is the complement of H^+(0, -p(\pi)) (up to the line itself, which has measure zero), and p(\pi) = -p(0) preserves the bisection for \mu_1.^[1] If f(0) = 0, then the line at \theta = 0 bisects both measures. Otherwise, f(0) and f(\pi) have opposite signs. By the intermediate value theorem, there exists \theta \in (0, \pi) such that f(\theta) = 0, so the line defined by \theta and p(\theta) bisects \mu_2 as well. This line therefore simultaneously bisects both \mu_1 and \mu_2.^[1] This argument, known as the rotating knife method, relies on the topology of the circle of directions and avoids advanced tools like the Borsuk–Ulam theorem required for higher dimensions. The compact support handles potential infinities by ensuring measures are well-behaved under line translations.^[1]

General n-Dimensional Proof

The general n-dimensional proof of the Ham Sandwich Theorem relies on the Borsuk--Ulam theorem, a fundamental result in algebraic topology. The Borsuk--Ulam theorem states that for any continuous function f: S^{d-1} \to \mathbb{R}^{d-1}, there exist antipodal points u, -u \in S^{d-1} such that f(u) = f(-u) ^[18]. This theorem provides the topological guarantee needed to ensure the existence of a bisecting hyperplane. To apply this to the Ham Sandwich Theorem in \mathbb{R}^d for d finite Borel measures \mu_1, \dots, \mu_d with finite total mass, hyperplanes are parameterized by their oriented normal vectors u \in S^{d-1}. For each u, the hyperplane is defined as H_u = \{ x \in \mathbb{R}^d \mid \langle u, x \rangle = t \}, where the threshold t is chosen such that the d-th measure \mu_d is bisected: \mu_d(\{ x \mid \langle u, x \rangle \geq t \}) = \mu_d(\mathbb{R}^d)/2 ^[18]. Let H_u^+ = \{ x \mid \langle u, x \rangle \geq t \} denote the closed half-space containing the "positive" side. A continuous function g: S^{d-1} \to \mathbb{R}^{d-1} is then defined with components

g_i(u) = \mu_i(H_u^+) - \frac{\mu_i(\mathbb{R}^d)}{2}, \quad i = 1, \dots, d-1.

The continuity of g follows from the dominated convergence theorem applied to the characteristic functions of the half-spaces, as the measures are finite ^[18]. Moreover, g is an odd function: g(-u) = -g(u). This holds because the choice of t for -u ensures the half-space H_{-u}^+ is the complement of H_u^- (up to the hyperplane itself, which has measure zero), swapping the measures in a way that negates the differences ^[18]. By the Borsuk--Ulam theorem, there exists u \in S^{d-1} such that g(u) = g(-u). Since g is odd, this implies g(u) = -g(u), so g(u) = 0 ^[18]. Thus, each g_i(u) = 0 for i=1,\dots,d-1, meaning the hyperplane H_u bisects \mu_1, \dots, \mu_{d-1}. By construction, it also bisects \mu_d. Note that the hyperplanes H_u and H_{-u} coincide, as they differ only in orientation. The antipodal symmetry ensures balance: swapping u and -u interchanges the half-spaces, forcing the measure differences to average to zero at the fixed point ^[18]. This topological approach generalizes the two-dimensional case, where the sphere S^1 parameterizes lines and the function maps to \mathbb{R}^1 ^[18].

Generalizations

Measure-Theoretic Extensions

The Stone-Tukey theorem, introduced in 1942, extends the classical ham sandwich theorem to encompass signed measures and measures with infinite total mass, broadening its applicability beyond the original requirement of non-negative finite measures. This generalization employs oriented simplices as a key geometric construct to facilitate simultaneous bisection. The theorem extends to signed Borel measures with finite total variation, where a single hyperplane simultaneously bisects all d measures. The proof employs oriented simplices to handle the topological argument via the Borsuk–Ulam theorem.^[7]^[19] A pivotal result in these extensions is that any collection of d measures, whether positive or signed, on \mathbb{R}^d can be simultaneously equipartitioned using a hyperplane arrangement, dividing the space into regions where each measure is equally distributed across the cells. For instance, when d is a power of 2, up to d n measures can be bisected into equal parts by an n-element hyperplane arrangement, with each cell receiving \frac{1}{2^n} of the total mass for every measure. This contrasts with the single-hyperplane bisection of the original theorem and enables finer partitions while accommodating signed measures through perturbations or direct topological arguments based on the Borsuk–Ulam theorem.^[20]^[21] These measure-theoretic extensions permit the treatment of negative densities, which arise naturally in contexts involving differences of positive distributions, and find applications in potential theory for analyzing potentials generated by signed measures. In such settings, the ability to bisect signed measures ensures balanced representations of charge distributions or discrepancies, facilitating the study of equilibrium problems and continuity properties of potentials.^[22]

Discrete and Computational Variants

The discrete variant of the ham-sandwich theorem addresses finite collections of points rather than continuous measures. Specifically, given d finite sets P_1, \dots, P_d of points in \mathbb{R}^d, possibly with multiplicities to account for weighted points, there exists a hyperplane that simultaneously bisects each set P_i, meaning that the number of points of P_i (counting multiplicities) on each open half-space is at most half the total, with equality if the total is even or differing by at most one if odd.^[23] This finite version follows from the continuous theorem via approximation arguments, where point sets are treated as Dirac measures, and the bisecting hyperplane can be perturbed to avoid passing through points if needed.^[24] Computing such a discrete ham-sandwich cut efficiently is a key challenge in computational geometry. In fixed dimension d, deterministic algorithms using topological sweep techniques achieve O(n \log n) time, where n is the total number of points, by reducing the search to traversing dual arrangements and applying parity arguments from the Borsuk-Ulam theorem.^[25] For d=2, optimal linear-time O(n) algorithms exist, often based on prune-and-search paradigms that iteratively eliminate candidate lines while maintaining balance.^[26] In higher dimensions, randomized algorithms leveraging linear programming solvers can find a bisecting hyperplane in expected O(n) time for d=3 under separation assumptions, with generalizations to O(n^{d-1}) worst-case for general d.^[24] A generalization, the \alpha-ham-sandwich theorem, extends the discrete setting to allow biased cuts: given \alpha = (\alpha_1, \dots, \alpha_d) with $0 < \alpha_i < 1, there exists a hyperplane such that each set P_i has exactly \alpha_i |P_i| points (or within one if not integer) in one specified half-space.^[27] Computing an exact \alpha-ham-sandwich cut is NP-hard in high dimensions d = \Omega(\log n / \log \log n), due to reductions from partition problems, but polynomial-time algorithms exist for fixed low d, such as O(n (\log n)^{d-3}) via dynamic programming on arrangements.^[28] A 2020 result provides the first non-trivial approximation scheme, computing a hyperplane that \varepsilon-approximates the \alpha-portions in polynomial time for fixed d and \varepsilon > 0, placing the problem in the complexity class UEOPL.^[29] These discrete and computational variants find applications in computational geometry for balanced data partitioning, such as dividing point clouds for parallel processing or clustering while respecting multiple measures.^[30] They also enable exact solutions in geometric arrangements, where ham-sandwich cuts serve as separators to simplify subdivision hierarchies or compute Voronoi diagrams under multiple criteria.^[31]

Recent Developments

In 2022, Pavle V. M. Blagojević, Florian Frick, and colleagues introduced transversal generalizations of the ham sandwich theorem, extending it to hyperplanes that are transversal to given manifolds while simultaneously bisecting measures and avoiding intersections with specified submanifolds.^[32] This framework applies to families of compact convex sets, ensuring that every member of each family is pierced by the union of hyperplanes from a transversal arrangement that equipartitions the measures.^[32] A 2024 elementary proof of the ham sandwich theorem, developed by Alfredo Hubard and Pablo Soberón, avoids the Borsuk–Ulam antipodal theorem by employing a discrete parity argument based on deformations and weak convergence of measures.^[33] The approach constructs odd-point set measures with an odd number of bisecting hyperplane arrangements and shows that the parity remains invariant under continuous deformations, extending to general Borel probability measures via approximation.^[33] This method relies solely on basic topological invariants like the intermediate value theorem in higher dimensions, providing a simpler alternative to traditional topological proofs.^[33] In 2025, research published in the Transactions of the American Mathematical Society established complex analogues of the ham sandwich theorem in \mathbb{C}^d, leveraging central transversal theorems to guarantee hyperplanes that bisect multiple complex measures while linking to the Tverberg–Vrećica conjecture.^[34] These results extend recent real-valued enhancements, offering tools for equipartitions in complex geometric settings.^[34] Also in 2025, Florian Frick and Zoe Wellner developed colorful variants of the Borsuk–Ulam theorem in the Journal of Fixed Point Theory and Applications, yielding multicolor extensions of the ham sandwich theorem for d+1 families of Borel probability measures on \mathbb{R}^d.^[35] The theorem ensures the existence of a hyperplane where each measure in a family achieves a positive halfspace mass under permutation conditions, generalizing to equitable subdivisions of multicolored point sets or measures.^[35] This specializes to strengthened uncolored versions, including results on avoiding certain halfspace configurations.^[35] Recent implications of the ham sandwich theorem include its application to gerrymandering analysis, as discussed in a 2024 Scientific American article, where it demonstrates that straight-line district boundaries cannot prevent partisan bias in voter distributions.^[8] For instance, in a state with uneven party support, the theorem guarantees bisecting lines that create districts with equal voter counts but disproportionate representation, underscoring limitations of geometric constraints on redistricting.^[8] Updates on computational complexity for α-cuts in the α-ham sandwich problem, from a 2020 analysis by Man-Kwun Chiu, Aruni Choudhary, and Wolfgang Mulzer, place the search problem of finding an α-bisecting hyperplane in the complexity class UEOPL for fixed dimensions.^[36] This provides the first non-trivial upper bound beyond PPAD-membership for the standard case, highlighting existential theory of the reals as a barrier in high dimensions.^[36] Generalizations to algebraic surfaces involve cuts that bisect volumes bounded by algebraic hypersurfaces, building on polynomial partitioning techniques to handle non-linear boundaries in equipartition problems.^[37]

References

[1]
Ham Sandwich Theorem -- from Wolfram MathWorld
The volumes of any n -dimensional solids can always be simultaneously bisected by a (n-1) -dimensional hyperplane. Proving the theorem for n=2 ...
[2]
[PDF] Ham Sandwich Theorem and Other Adventures in Topology
The Ham Sandwich Theorem states that three bounded 3D objects can be cut in half simultaneously with one cut.
[3]
The Early History of the Ham Sandwich Theorem - ResearchGate
The starting point for our investigation is the classical Ham Sandwich theorem conjectured by Steinhaus and proved by Banach (see [3] ), a result which is at ...
[4]
Generalized "sandwich theorems - Project Euclid
GENERALIZED "SANDWICH THEOREMS. Bc A. H. STONE AND J. ro TUKEY. The following theorem is wellknown under the self-explanatory name of the "ham sandwich ...
[5]
A ham sandwich theorem for general measures
A Ham Sandwich Theorem for General Measures. G. W. Cox t and R. D. McKelvey 2. 1 University of Texas at Austin, Texas 78712, USA. 2 California Institute of ...
[6]
Generalized “sandwich” theorems - Project Euclid
June 1942 Generalized “sandwich” theorems. A. H. Stone, J. W. Tukey · DOWNLOAD PDF + SAVE TO MY LIBRARY. Duke Math. J. 9(2): 356-359 (June 1942).
[7]
The Strangely Serious Implications of Math's 'Ham Sandwich Theorem'
Feb 17, 2024 · Math's “ham sandwich theorem” promises that for any three (potentially asymmetrical) objects in any orientation, there is always some straight cut that can ...Missing: original | Show results with:original
[8]
[PDF] Algorithms for the 2D ham sandwich problem
Given two disjoint sets P1 and P2 in R2, a two-dimensional ham sandwich cut is a line that bisects both P1 and P2 simultaneously. The ham sandwich problem.
[9]
[PDF] the borsuk-ulam and ham sandwich theorems - UChicago Math
Aug 22, 2008 · The functions which go from the topology of one space to the topology of another are called continuous. Likewise we can talk about functions ...Missing: interpretation | Show results with:interpretation
[10]
[PDF] Ham Sandwich Theorem | City Tech OpenLab
While most statements of the ham sandwich theorem stipulate that the sliced objects must have the property of compactness, or that they must be bounded ...
[11]
[PDF] Ham Sandwich is Equivalent to Borsuk-Ulam - DROPS
In this paper, we demonstrate the equivalence between the Borsuk-Ulam theorem and the. Ham Sandwich theorem. The main technical result we show towards ...Missing: seminal interpretation<|control11|><|separator|>
[12]
Pancake sorting - Wikipedia
Pancake sorting is the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stackMissing: unsolved | Show results with:unsolved
[13]
Before Microsoft, Gates Solved A Pancake Problem - NPR
Jul 4, 2008 · And you have to figure out a series of flips that will sort the stack so that you get the biggest pancake on the bottom, the second biggest one ...
[14]
[PDF] Transversal Generalizations of Hyperplane Equipartitions
The classical Ham Sandwich theorem states that any d point sets in Rd can be simul- taneously bisected by a single affine hyperplane.
[15]
Slicing Sandwiches, States, and Solar Systems | American Scientist
According to the two-dimensional (pizza) version of the ham sandwich theorem, there is a straight line across the United States so that exactly half of the ...<|control11|><|separator|>
[16]
Earliest Known Uses of Some of the Words of Mathematics (H)
HYPOTENUSE was used by Pythagoras (c. 540 BC). It is found in English in 1571 in A geometrical practise named Pantometria by Thomas Digges (1546?-1595).
[17]
[PDF] The Second Book of Mathematical Puzzles and Diversions
With mathematical commentaries by Mr. Gardner, ripostes from readers of Scientific American, references for further reading and, of course, solutions.
[18]
[PDF] Jirı Matoušek - Using the Borsuk–Ulam Theorem
This book aims at making elementary topological methods more easily accessible to nonspecialists in topology. It covers a number of substantial combinatorial ...
[19]
Cutting the Same Fraction of Several Measures
Aug 9, 2012 · The famous “ham sandwich” theorem of Stone, Tukey, and Steinhaus [13, 14] asserts that every d absolutely continuous probability measures in ...
[20]
Bisecting measures with hyperplane arrangements - ResearchGate
Aug 6, 2025 · ... hyperplane arrangement that bisects each of the measures into equal halves simultaneously. ... The proof of the ham sandwich theorem uses the ...
[21]
Continuity and maximum principle for potentials of signed measures
"Continuity and maximum principle for potentials of signed measures." Czechoslovak Mathematical Journal 25.2 (1975): 309-316. ... potential theory, Wiley- ...
[22]
[PDF] DP Dobkin" (Princeton), H. Edelsbrunner" (Graz) Ham-Sandwich ...
The discrete ham-sandwich theorem is now: Theorem 1: Let P₁.....P be finite sets of points in E. There is a plane that ...
[23]
Algorithms for ham-sandwich cuts
Lo and W. L. Steiger. An optimal time algorithm for ham-sandwich cuts in the plane. Proc. 2nd Canadian Conference on Computational Geometry, 1990, pp. 5- ...
[24]
Algorithms for ham-sandwich cuts | Discrete & Computational ...
Apr 1, 1994 · We present algorithms for finding ham-sandwich cuts in every dimensiond>1. Whend=2, the algorithm is optimal, having complexityO(n). For ...
[25]
Algorithms for ham-sandwich cuts - ACM Digital Library
We present algorithms for finding ham-sandwich cuts in every dimensiond>1. Whend=2, the algorithm is optimal, having complexityO(n).
[26]
[PDF] Computational Complexity of the α-Ham-Sandwich Problem - arXiv
Mar 20, 2020 · The classic Ham-Sandwich theorem states that for any d measurable sets in Rd, there is a hyperplane that bisects them simultaneously. An ...
[27]
Computational Complexity of the $α$-Ham-Sandwich Problem - arXiv
Mar 20, 2020 · We show that for the \alpha-Ham-Sandwich theorem, the search problem of finding the dividing hyperplane lies in UEOPL.
[28]
Computational Complexity of the α-Ham-Sandwich Problem - DROPS
Jun 29, 2020 · The computational complexity of this search problem in high dimensions is open, quite unlike the complexity of the Ham-Sandwich problem, which ...
[29]
[PDF] Dynamic Ham-Sandwich Cuts in the Plane - UCSD CSE
credits Hugo Steinhaus for posing the ham-sandwich problem and credits Stefan Banach for first solving the problem via a reduction to the Borsuk-Ulam ...
[30]
[PDF] Ham-Sandwich Cuts for Abstract Order Types - TU Berlin
Lo, C.Y., Matoušek, J., Steiger, W.: Algorithms for ham-sandwich cuts. Discrete Com- put. Geom. 11, 433–452 (1994). 31. Lo, C.Y., Steiger, W.: An optimal ...
[31]
[2210.15423] Transversal generalizations of hyperplane equipartitions
Oct 27, 2022 · Abstract page for arXiv paper 2210.15423: Transversal generalizations of hyperplane equipartitions.Missing: Blagojević date
[32]
[2404.14320] Bisecting masses with families of parallel hyperplanes
Apr 22, 2024 · Our main result implies the ham-sandwich theorem, the necklace splitting theorem for two thieves, a theorem about chessboard splittings with ...
[33]
AMS :: Transactions of the American Mathematical Society
These theorems yield complex analogues of recent extensions of the ham sandwich theorem ... © Copyright 2025 American Mathematical Society; Journal: Trans ...
[34]
https://www.ams.org/journals/tran/0000-000-00/S0002-9947-2025-09555-2/
[35]
[PDF] Computational Complexity of the α-Ham-Sandwich Problem - DROPS
Abstract. The classic Ham-Sandwich theorem states that for any d measurable sets in Rd, there is a hyperplane that bisects them simultaneously.
[36]
The Kakeya conjecture and the Ham Sandwich theorem - Terry Tao
Nov 27, 2008 · In this post I would like to sketch some of the key ideas in Guth's paper, in particular the role of the Ham Sandwich theorem (or more precisely ...Missing: original | Show results with:original<|control11|><|separator|>