A survey of mass partitions
Abstract
Mass partition problems describe the partitions we can induce on a family of measures or finite sets of points in Euclidean spaces by dividing the ambient space into pieces. In this survey we describe recent progress in the area in addition to its connections to topology, discrete geometry, and computer science.
1. Introduction
Mass partition problems study how partitions of Euclidean spaces split families of measures. For example, for a given measure, how can the total space be split so that each part has the same measure while satisfying some additional geometric property? These problems are also referred to as measure partition problems or equipartition problems. The quintessential example is the ham sandwich theorem. Informally, this theorem states that a (three-dimensional) sandwich made out of three ingredients may be split fairly among two guests using a single straight cut.
Mass partition problems are at the crossroads of topology, discrete geometry, and computer science. These problems usually appear while studying discrete geometry and provide a natural field to test tools from equivariant topology. The explicit computation of fair partitions of finite point sets is an exciting challenge, and many such results can be applied to geometric range searching. Furthermore, mass partitions have been used successfully to solve hard problems in seemingly unrelated areas, such as incidence geometry.
Surveys that cover mass partitions often focus on the topological Reference Ste85Reference Mat03Reference Živ17Reference DLGMM19Reference BFHZ18 or computational Reference Ede87Reference AE99Reference Mat02Reference KK03Reference KU20 aspects of this area. The purpose of this survey is to give a broad overview of mass partition theorems and recent advances in this area.
A large family of results related to mass partitions is fair partitions, particularly cake splitting problems. These problems often deal with partitions of an interval in according to several players’ subjective preferences (which may or may not be induced by measures). In this survey, we focus on results where the geometry of the ambient space plays a key role. We only dwell on interval partitions when they have some interesting higher-dimensional extension. We recommend Reference Wel85Reference BT96Reference Su99Reference Bar05Reference Pro15 and the references therein for different variations of fair partitions, their applications, and methods to obtain them.
The general form of mass partition problems is the following.
For example, in the ham sandwich theorem, is the set of partitions of into two parts by a single hyperplane. In most cases we seek to split each measure into parts of equal size. If is fixed, an interesting parameter is the maximal cardinality of for which Problem 1.0.2 has an affirmative answer. The ham sandwich theorem is optimal in this sense. If we consider measures, each concentrated near one of the vertices of a simplex, no hyperplane can simultaneously halve all of them.
We consider several families which lead to interesting problems. These include partitions by several hyperplanes, partitions into convex pieces, partitions with low complexity algebraic surfaces, partitions by cones, and more.
1.1. History
It is hard to say precisely when the study of mass partition problems started. For example, the ham sandwich theorem in dimension one is equivalent to the existence of the median in probability. Early results dealt with splitting the volume of convex bodies into equal parts, rather than general measures. Most proofs can be extended to deal with measures with minor modifications.
If we focus on results in dimension greater than one, Levi published the first mass partition result in 1930, regarding translates of cones Reference Lev30.
Levi also proved two other mass partition theorems in dimension two using continuity arguments. One of these results is the two-dimensional version of the ham sandwich theorem. The other is that for any convex body in the plane we can always find three concurrent lines forming at angles of each of which halves the area of the convex body. ,
The ham sandwich theorem appeared in the 1930s. It was conjectured by Steinhaus. In 1938 Steinhaus presented a proof for the case and attributed it to Banach Reference Ste38 (see Reference BZ18 for a translation). The problem itself is listed as Problem 123 of The Scottish Book Reference Mau81, where mathematicians in Lwów, Poland, would gather problems, conjectures, and solutions. The Scottish Book is named after the Scottish Café, where meetings were held. Shortly after, Stone and Tukey proved the ham sandwich theorem in its general form Reference ST42.
Steinhaus gave another, quite different, proof of the ham sandwich theorem in dimension three in 1945 Reference Ste45, using the Jordan curve theorem. According to Reference BZ18, this work was done while Steinhaus was in hiding during World War II.
In Courant and Robbins’s 1941 book Reference CR41, p. 317 there are a few results regarding divisions of planar convex bodies. For example, you can split a convex body into four parts of equal area using two straight lines. It is clear from the text that the authors were aware of the ham sandwich theorem and its relation to these results. Buck and Buck generalized this result by showing that you can split any convex body into six parts of equal area using three concurrent lines Reference BB49. This is the first time that the term equipartition was used.
These were the first results on mass partitions. Since then, the area has been greatly developed. One of the main goals is to find natural or useful families of partitions for which an equipartition of several measures is always guaranteed to exist.
1.2. Continuous and discrete versions
Mass partition theorems are usually stated in one of two settings: discrete or continuous. Figure 1 shows an example of each kind. In the discrete setting, we work with finite families of points. Some conditions are imposed to avoid degenerate partitions, i.e., those that have many points in the boundary between parts.
A set of points in is in general position if no of them lie on a single hyperplane. For a finite set in general position, we say that a hyperplane halves if either is even and each open side of contains exactly points of or if , is odd and each open side of contains exactly points of Then, we can state the discrete ham sandwich theorem. .
The continuous versions deal with measures in In older papers, the measures usually came from a density function or the volume measure of some convex region in . However, most of those results can be proved for more general measures with only minor modifications to the original proofs. Some proofs even extend to charges, which can assign negative values to subsets of . .
We say that a measure in is absolutely continuous if it is absolutely continuous with respect to the Lebesgue measure. We say that is finite if is finite. The condition of absolute continuity is imposed to avoid worrying about the boundary between sections of a partition, as it has measure zero for most families of partitions we consider. It also has the benefit that the functions involved in topological proofs, as described in the next subsection, are continuous. In some cases (such as Theorem 1.2.2), the absolute continuity condition can be replaced by a weaker statement, such as for every hyperplane .
The connection between continuous and discrete versions of mass partition results can be argued by approximation arguments. A measure can be approximated by a sequence finite set of points of increasing size. A finite set of points can be approximated by a sequence of measures whose supports are balls centered at points of of decreasingly small radius. The equivalence, although common, is not entirely immediate. For some mass partition problems going from the continuous version to the discrete is a nuanced problem Reference BRSZ19. When such approximation arguments work, we immediately obtain mixed versions of mass partition results, in which some measures are concentrated in points and some are absolutely continuous.
To allow general measures or to avoid the general position assumptions, we need to modify the conclusion in our theorem Reference CM84. For example, a ham sandwich theorem for a family of general measures says the following. We can always find a hyperplane such that for any measure the two closed half-spaces and bounded by satisfy
A common degenerate family of measures where this is used is formed by sets of weighted points, which are linear combinations of Dirac measures.
1.3. Topological proof techniques
Mass partition problems are one of the best examples of combinatorial problems that can be solved using topological tools. A standard way to reduce combinatorial problems to topology is via the test map/configuration space (TM/CS ) scheme. This is a technique frequently used in topological combinatorics. For continuous mass partition problems, it consists of the following steps.
- •
First, we define a topological space often called the configuration space. This space parametrizes a space of partitions related to our problem. ,
- •
Second, we construct a topological space which describes how an element of , splits each measure. There should also be a natural function called the test map. The smoothness conditions on the measures are typically required to make this map continuous. It is common for , to be real space and for to be built so that any is a solution to the problem.
- •
Third. Ideally, the symmetries of the problem imply that there is a group acting on and This is usually chosen so that the map . is equivariant. In other words, for every and we have ,
- •
Finally, we reduce the mass partition problem to a property of continuous maps -equivariant Proving that all such maps satisfy the desired property is done as a purely topological problem. .
Ultimately, the choice of space determines the topological problem in the last step. Let us prove the ham sandwich theorem to exemplify this method. The topological tool we use is the Borsuk–Ulam theorem.
In the proof above, the space of partitions was parametrized by The group acting on . is with the antipodal action. The parametrization makes and correspond to complementary half-spaces. Different mass partition results lead us to use more elaborate configuration spaces and group actions Reference Živ17Reference BFHZ18Reference Mat03. The use of the Borsuk–Ulam theorem in this proof is mostly unavoidable, as the ham sandwich theorem is equivalent to the Borsuk–Ulam theorem Reference KCS17. The fact that a sphere parametrizes the set of half-spaces will be used repeatedly throughout this survey.
A common generalization of the Borsuk–Ulam theorem used in this proof scheme is the following theorem. We say that the action of a group on a topological space is free if the equation implies that is the neutral element of .
The advantage of the theorem above is that we only need to know the connectedness of and the dimension of to apply it.
1.4. Computational complexity
Topological proofs provide a clear and elegant way to tackle mass partition problems. However, these are all existence proofs, giving us little information about how to find such partitions.
In the discrete versions of mass partitions results, we want to split several finite families of points in in a predetermined manner. If the total number of points is an algorithm to find such a partition with running time in terms of , is desirable. Moreover, since mass partitioning results have applications in computer science, finding such algorithms is more than an academic exercise. A fundamental case is the problem of finding ham sandwich partitions.
The search space for such an algorithm has size as that is the number of different subsets of , an affine hyperplane can cut off.
In the plane, Lo, Matoušek, and Steiger Reference LMS94 presented algorithms that run in time, which is optimal. If the points are weighted, then a ham sandwich cut can be computed in time Reference BL05. In dimension three, algorithms that run in time, up to poly-logarithmic factors, are known Reference LMS94.
In high dimensions, the current best algorithms run in time Reference LMS94. For comparison, the problem requires time Reference LMS94. Geometric conditions can sharply reduce the computational complexity. If we impose a separation condition on the convex hulls of each of as considered by Bárány, Hubard, and Jerónimo Reference BHJ08, then a ham sandwich cut can be found in time, regardless of the dimension Reference Ber12 (more general cuts can be found in time Reference SZ10). In dimension two, some algorithms dynamically maintain ham sandwich cuts for two sets of points subject to successive insertion or deletion of points Reference ABC 09. The discrete ham sandwich problem, where the dimension is part of the input, is PPA-complete Reference GFR19. This complexity class (short for Polynomial Parity Argument) was introduced by Papadimitriou Reference Pap94 and is related to the problem of finding a second vertex of odd degree in a graph where one such vertex is known to exist.
In general, the algorithmic complexity of the results in this survey is much better understood in dimensions two and three. Every mass partition problem has an associated algorithmic variant, which is worth pursuing.
1.5. Applications
One of the principal applications of mass partition results is to give structure to geometric data. This is often the case when dealing with geometric range queries. Suppose we are given a finite family of points in which is fixed. Then, we will be given a set , and might be interested in either
- •
how many points of are contained in or ,
- •
a list of the points of contained in .
If we want to solve this problem for a particular set we need to check one by one the points of , to see if they are contained in However, if we intend to solve this problem for a sequence of sets, called ranges, . it is possible we find improved algorithms if the sets satisfy interesting geometric conditions. Such conditions include being a half-space, a simplex, or an axis-parallel box.
We can use mass partition results to preprocess the set and allow us to solve these problems efficiently. The first use of partition results of this kind goes back to Willard Reference Wil82 using partition trees for simplex range searching. The idea is to apply a mass partition result to and split it into sets Then, the mass partition result is applied to each of the . We continue to do so and obtain a . tree structure on -ary Depending on the geometric properties of the ranges, such a tree structure can allow us to answer ranges queries efficiently. Many of the results discussed in Section .3.3 were designed to solve half-space and simplex range queries this way, such as the Yao–Yao theorem Reference YY85. Queries in which the ranges are half-spaces are relevant in database searching.
Approximate partitions are often sufficient for these problems but are easier to compute Reference HW87Reference Mat92. Other partition results, such as the cutting lemma (Theorem 3.3.5), also have strong applications in computational geometry. We recommend Agarwal and Erickson’s survey on geometric range queries for more on this topic Reference AE99.
The ham sandwich theorem also has applications in voting theory Reference CM84, and some of its extensions can be applied to congressional district drawing Reference Hum11Reference Sob17. Section 2.4 contains some examples of purely combinatorial problems in which mass partition problems are relevant. In the next sections, we discuss the applications to other problems in discrete geometry, such as incidence geometry (Section 3.3) and geometric Ramsey theory (Section 5.2).
2. Partitions by multiple hyperplanes
In the ham sandwich theorem, the partitions we seek are given by a single hyperplane. As hyperplanes are easy to parametrize, it is convenient to look at partitions induced by several hyperplanes. The combinatorics of the complement of hyperplane arrangements has been extensively studied Reference Zas75Reference OT92. They provide rich configuration spaces for mass partition problems.
2.1. The Grünbaum–Hadwiger–Ramos problem
A family of hyperplanes in is in general position if no of them are concurrent, and any of their normal vectors are linearly independent. If we are given affine hyperplanes in in general position and then they split , into regions. We are interested in partitions of this type where each of the parts has the same size for many measures, simultaneously.
Grünbaum asked if it is possible to find such a partition for a single measure and hyperplanes Reference Grü60. This is simple for and is known for Reference Had66Reference YDEP89. For there is a continuum of equipartitions of this type, and additional conditions may be imposed. Avis Reference Avi84 showed that we cannot guarantee the existence of hyperplanes that split a single measure into equal parts for It suffices to consider a measure concentrated around points on the moment curve . in a family of ; hyperplanes intersects the moment curve in at most points, which less than the cuts needed to guarantee the desired partition. Because of this, Ramos proposed the following problem.
This is now known as the Grünbaum–Hadwiger–Ramos mass partition problem. Ramos extended Avis’s argument to show that the condition is necessary, and made the following conjecture Reference Ram96.
The best general upper bound for this problem is by Mani-Levitska, Vrećica, and Živaljević Reference MLVŽ06.
Grünbaum’s problem is settled in all dimensions except which leaves the following question open. ,
The natural configuration space of a set of hyperplanes in is a , direct product of -fold spheres. This space does not have the connectedness needed for simple topological approaches to yield strong results; for instance, we cannot obtain interesting results by applying Theorem -dimensional1.3.2. The subtleties of the topological tools needed, as well as an excellent description of different ways to approach this problem, is best explained in the recent survey of Blagojević, Frick, Haase, and Ziegler Reference BFHZ18. Further advances can also be found in Reference BFHZ16. Vrećica and Živaljević proposed a different approach to fix some issues raised by the survey from Blagojević et al. in Reference VŽ15.
The algorithmic aspect of Problem 2.1.1 is interesting. We can split a set of points in the plane into four parts of equal size using two lines, and the two lines can be found in time Reference Meg85. If we want the two lines to be orthogonal, they can be found in time Reference RS07. The orthogonality condition yields another variant of this problem in high dimensions, where the hyperplanes must be pairwise orthogonal.
The best bounds for the orthogonal case were proved by Simon Reference Sim19. If we relax the conditions on the partition, we can obtain sharp results. Makeev proved that for any absolutely continuous measure in we can find pairwise orthogonal hyperplanes such that any two of them split into four equal parts Reference Mak07. Additionally, the orthogonality condition may be dropped to extend the equipartition to two centrally symmetric measures. To be precise, for any two absolutely continuous measures in which are centrally symmetric around the origin there are hyperplanes such that any two of them split both and into four equal parts.
2.2. Successive hyperplane partitions
A different variation of the Grünbaum–Hadwiger–Ramos problem appears if we don’t allow the hyperplanes to extend indefinitely. We say a partition is a successive hyperplane partition of if it can be constructed in the following way. First, use a hyperplane to split into two parts. Then, if is split into parts for some use a hyperplane to cut exactly one of the parts into two. A successive hyperplane partition of , into parts always uses hyperplanes.
It is easy to see that must be even to split simultaneously two absolutely continuous measures in into equal parts using a successive hyperplane partition of For an odd number of parts, consider two uniform measures on concentric spheres of different radii. If there was such an equipartition, the first hyperplane must leave a . fraction of each measure on one side and an fraction on the other, for some integer which is not possible. It is not clear if the parity of , is the only obstacle.
For the case when , are (respectively) uniformly distributed in two convex sets with was solved affirmatively by Fruchard and Magazinov Reference FM16.
Consider a sphere in centered at the origin. If we construct a successive hyperplane partition whose hyperplanes all contain the origin, we obtain a partition of the sphere by great circles. Such partitions were used by Gromov to find convex partitions of spheres Reference Gro03 with additional constraints. Other results involving successive hyperplane partitions are described after Problem 2.4.3.
2.3. Bisections by hyperplane arrangements
An alternate distribution induced by affine hyperplane arrangements is to split into two sets by a chessboard coloring, as shown in Figure 3. Given a finite family of affine hyperplanes, we can choose arbitrarily for each its positive half-space and its negative half-space This generates a partition of . into two parts defined by
High-dimensional results of this kind were proved by Alon and West Reference AW86. The partitioning hyperplanes were restricted: only hyperplanes orthogonal to the elements of the canonical basis were allowed, and the partition must remain invariant after reorderings of the canonical base. They showed that, if is an odd positive integer, it is possible to split any measures using cuts for each coordinate axis.
A less restrictive result is obtained if we only fix the direction of each hyperplane. If we declare that there must be hyperplanes orthogonal to the element of the canonical basis, then Karasev, Roldán-Pensado, and Soberón showed that th measures may be split whenever the multinomial coefficient
is odd Reference KRPS16. This last condition is equivalent to and not sharing a in the same position of their binary expansions.
If we completely remove the conditions on the hyperplanes, one would expect to be able to partition more measures. The following conjecture by Langerman was presented by Barba, Pilz, and Schnider Reference BPS19 when they solved the case positively.
This conjecture has been verified when is a power of by Hubard and Karasev Reference HK19. If is odd and is a power of it was shown that , measures can be simultaneously split into two equal parts by hyperplanes Reference BBK18. Schnider proved a different relaxation of Conjecture 2.3.1, namely, he proved the following result Reference Sch20.
We include a simple proof of the following weaker form of Conjecture 2.3.1 for This result will be used in Section .3.4 and showcases the methods and obstacles involved in solving Conjecture 2.3.1. The methods of Reference HK19Reference BBK18 imply Theorem 2.3.3 with measures instead of measures if We discuss this improvement after the proof. For large values of . the number of measures can be increased to , Reference BBK18.
The reason we lost the ability to split one measure fewer than Reference HK19Reference BBK18 is that we are not using all the properties of In our construction, notice . yet this is not used in the proof above. Hubard and Karasev prove that adding this to the group action changes the topological obstruction and allows us to split one more measure. ,
2.4. Necklace splitting
The name for this family of partition results comes from the following setting. Suppose thieves steal an unclasped necklace with types of beads. The number of beads of each kind is a multiple of They want to cut the necklace into several strings and distribute the strings among themselves so that each thief has the same number of beads of each kind. What is the minimum number of cuts needed to obtain such a partition? Figure .4(b) shows how to construct examples that require cuts, by placing the beads in monochromatic intervals. Each interval requires at least cuts. In 1987, Alon proved that cuts were always sufficient Reference Alo87. He proved both the continuous and discrete versions of this result. In the continuous version, the set of beads of a given color is replaced by a finite absolutely continuous measure on .
Hobby and Rice first proved the continuous version for Reference HR65. Goldberg and West then proved the discrete version for Reference GW85, and a second proof was presented by Alon and West Reference AW86. The discrete version is a completely combinatorial problem: the number of beads of each kind and the order in which they come determine the problem. Nevertheless, the proofs for the vast majority of cases are essentially topological (say, using discrete analogues of standard topological machinery Reference Pál09Reference Meu14). The cases for and any and for , and any admit inductive proofs Reference Meu08Reference AFP 18.
The computational complexity for the discrete necklace problem has been recently settled. In the case it is PPA-complete ,Reference GFR19. This complexity class often appears with problems related to the Borsuk–Ulam theorem Reference Pap94. For the discrete necklace problem is related to the , complexity classes, which extend PPA from parity arguments to modulo arguments Reference Hol19Reference FRHSZ20Reference GKSZ19. Efficient approximation algorithms have been found if the thieves are satisfied with a smaller portion of each kind of bead, yet still proportional to Reference AG20.
We present two proofs of Theorem 2.4.1 for to illustrate the main ideas behind this family of results.
In the first proof of the Hobby–Rice theorem, Asada et al. observed that we may use other results regarding partition by hyperplane arrangements (such as those from the Grünbaum–Hadwiger–Ramos problem) instead of the ham sandwich theorem. We can therefore impose additional conditions on the necklace splittings Reference AFP 18Reference JPŽ20.
Even though there are examples of necklaces that require cuts, sometimes fewer cuts are sufficient. For the case the case of partitions by , cuts yields interesting results Reference Sim08, and partitions by cuts may be very hard to obtain Reference AGLM09Reference Las15. Deciding if a necklace with kinds of pearls can be distributed among two thieves using fewer than cuts is an NP-complete problem Reference Meu08.
There are several high-dimensional extensions of the necklace splitting theorem, depending on which partitions we consider for If we are given . measures in the unit cube it was proved by de Longueville and Živaljevic that it is possible to distribute them among , thieves by using cuts by hyperplanes parallel to the facets of the hypercube and then distributing the pieces, even if the number of cuts parallel to each facet is fixed in advance Reference DLŽ08; see Figure 5.
Instead of optimizing the number of hyperplanes used to make the partition, we can reduce the number of parts into which we split if we restrict our attention to convex pieces. ,
Theorem 2.4.1 implies If the partitions are made by successive hyperplanes with directions fixed in advance, and each hyperplane only cuts one part, Karasev, Roldán-Pensado, and Soberón showed that . Reference KRPS16. Blagojević and Soberón proved that so the thieves can use the dimension to their advantage ,Reference BS18b.
The discrete necklace splitting theorem is a surprising application of the ham sandwich theorem to a completely combinatorial problem. The following extension of a problem for the All-Russian Mathematical Olympiad 2005 provides another example Reference BCK05.
If each type of fruit is distributed evenly among an odd number of baskets and no basket contains more than one kind of fruit, we can see that the solution above yields an optimal bound. The original problem was the case , which can be solved by purely combinatorial methods as well. ,
3. Convex partitions of
If we seek to split into more than one piece, we can ask for the parts to be convex. We say that is a convex partition of into parts if
- •
every set is a closed and convex subset of ,
- •
the union of all equals and ,
- •
the interiors of any two are disjoint if .
Many natural partitions of such as partitions induced by hyperplane arrangements, are convex partitions. Yet, the space of convex partitions of , into parts is hard to parametrize Reference LZ18. Several proofs concerning convex partitions of instead use a subset of those partitions that are easier to parametrize: generalized Voronoi diagrams, also called power diagrams.
Given a family of different points in denoted sites, and , real numbers we can define the , functions
Then, we consider the sets It is a simple exercise to show that these sets form a convex partition of . If . we have a Voronoi diagram. If we fix the points , and an absolutely continuous finite measure we can find values , such that the values match any numbers we want, provided they sum to Reference AHA98. We use this result again in Section 4.2. The space of possible of different points is the standard configuration space of -tuples which is widely used in algebraic topology ,Reference Knu18.
The natural question of whether the ham sandwich theorem extends to convex partitions of leads to the following theorem.
The case was proved independently three times Reference IUY00Reference BKS00Reference Sak02, and it generalizes earlier results on “perfect partitions of a cake” Reference ANRCU98Reference AKK 00. The general case also has three different proofs Reference Sob12Reference KHA14Reference BZ14. The proof for the planar case by Bespamyatnikh, Kirkpatrick, and Snoeyink involves the discrete version of this result, and gives an algorithm to construct the partition in time where is the total number of points to split. If the point set is contained in a polygonal region (not necessarily convex), similar results can be obtained Reference BBK06.
Theorem 3.0.1 can be applied to congressional district drawing Reference Hum11Reference Sob17 in the context of gerrymandering, which is related to the application of the ham sandwich theorem to voting theory Reference CM84. Another application is the following extension of Example 2.4.4.
3.1. The Nandakumar–Ramana Rao problem
Even though Theorem 3.0.1 deals with fair partitions of measures, the proofs of Karasev, Hubard, and Aronov and of Blagojević and Ziegler yield much more Reference KHA14Reference BZ14. They were motivated by a question of Nandakumar and Ramana Rao, which asked if every polygon in the plane could be split into convex parts of equal area and equal perimeter, for any positive integer If the polygon has . vertices, there are algorithms that find such a partition for in time Reference AD15.
The perimeter is not a measure, but it is a continuous function on all compact convex sets under the Hausdorff metric. In the plane, the first nontrivial case of the Nandakumar–Ramana Rao problem to be solved was Reference BBS10. The result stated below settled the problem for a prime power. It is nicknamed the spicy chicken theorem.
When the continuous functions are induced by measures (i.e., a simple subdivision argument yields Theorem ),3.0.1. Recently, Akopyan, Avvakumov, and Karasev settled the Nandakumar–Ramana Rao problem affirmatively for any Reference AAK18. Their high-dimensional theorem, stated below, also implies Theorem 3.0.1.
Avvakumov and Karasev extended closely related techniques to cover broader families of cake-cutting problems Reference AK20. A result related to Theorem 3.1.1 is relevant in the proof of the symmetric case of Mahler’s conjecture in Iriyeh and Shibata proved implicitly the following theorem, which was stated precisely later by Fradelizi, Hubard, Meyer, and Roldán-Pensado .Reference IS20Reference FHM 19.
As done previously, the planar sections’ areas may be replaced by a continuous function on the planes through the origin. It seems difficult to extend this theorem to higher dimensions. This is because the natural generalizations fail to give an adequate setting for the test map/configuration space scheme.
3.2. The Holmsen–Kynčl–Valculescu conjecture
In the results above, the number of measures to be split among the parts is equal to the dimension. This is optimal if we want to split each measure perfectly among each part of the partition. If we have more measures, Holmsen, Kynčl, and Valculescu made the following conjecture for finite sets of points Reference HKV17.
The case was proved in the same paper in which the conjecture was stated. The case was proved by Blagojević, Rote, Steinmeyer, and Ziegler Reference BRSZ19. They proved a stronger statement: a discrete version of Theorem 3.0.1 in high dimensions. The discrete version in the case had been proved earlier Reference IUY00Reference BKS00.
The case of Conjecture 3.2.1 is a known consequence of the ham sandwich theorem due to Akiyama and Alon Reference AA89. In particular, the planar case of this result implies that for any set of red points and blue points in the plane, there exists a perfect red-blue matching whose edges induce pairwise disjoint segments. For numerous extensions to noncrossing geometric graphs in the plane, we recommend the survey by Kano and Urrutia Reference KU20.
Kano and Kynčl’s hamburger theorem implies the case of Conjecture 3.2.1. The hamburger theorem describes mass partition results for measures using a single hyperplane Reference KK18.
Several continuous analogues of Conjecture 3.2.1 were proved by Blagojević, Palić, Soberón, and Ziegler Reference BPSZ19, such as the following result.
The value is optimal if additional constraints on the partition are imposed, such as splitting fairly of the measures. However, it would be interesting to know if the result is optimal in general.
3.3. Partitions and their transversals
If we are interested in partitions of into convex pieces, we can impose additional geometric conditions. For any partition of into pieces using hyperplanes, no hyperplane can intersect the interior of all parts. Even though it may be impossible to find fair partitions of a single measure using hyperplanes, Yao and Yao showed that the lack of a hyperplane transversal may be preserved Reference YY85 (see Reference Leh09 for a constructive proof).
The theorem above is motivated by its applications in geometric range queries (notably, half-space queries) as a way to preprocess data Reference AE99. The geometric conditions of the Yao–Yao theorem lead to interesting questions.
For it is known that , Reference RPS14. In the plane, for four parts are enough. For Buck and Buck’s ,Reference BB49 equipartition by three concurrent lines shows that at although equipartitions like the one in Figure ,6(a) also work. In those, we use two lines to split the measure in parts of size and then apply the ham sandwich theorem on the pieces of size , Another solution for . can be obtained using a partition by three lines, two of which are parallel Reference KRPS16. For we can use Schulman’s equipartition result with cobwebs to get , A cobweb consists of two intersecting lines . and four points (two in two in , in convex position. The four sides of the quadrilateral ) and divide the plane into eight regions. Figure 6(b) shows an example. Schulman showed that, for any absolutely continuous finite measure in the plane, we can find a cobweb that splits into eight equal parts Reference Sch93. The reader can verify that every line misses the interior of at least three regions.
Another interesting question is how to split more than one measure with similar geometric conditions. We need to decrease the dimension of the transversal to have a meaningful question.
The case is the Yao–Yao theorem, giving The case . is the ham sandwich theorem, giving It is tempting to conjecture that . However, this conjecture fails for . Any partition of . into four convex sets such that each line avoids the interior of at least one part is made by the intersection of two hyperplanes. Yet, the known bounds for Problem 2.1.1 show that at most measures can be split by two hyperplanes into four equal parts, as opposed to the we would need for this problem.
If we do not require a perfect partition of our measures or point sets, then stronger partitioning results can be obtained.
Notice that we no longer ask that the convex hulls of the parts be pairwise disjoint. This condition is replaced by the hyperplane avoiding condition. The algorithms used to find such partitions are important for geometric range queries.
We may also be interested in avoiding a particular family of hyperplanes as transversals instead of avoiding any possible hyperplane. Results such as the cutting lemma become important in this setting. The cutting lemma was proved independently by Chazelle and Friedman Reference CF90 and by Matoušek Reference Mat90 (see also Reference Cha93).
In the result above, the boundary of each part of the partition is contained in the union of at most three lines. The cutting lemma is also prominent due to its application to incidence problems Reference CEG 90, such as the Szemerédi–Trotter theorem.
Another family of partitioning results that are useful for incidence problems are polynomial partitioning theorems. One of the most notable examples is the following theorem that Guth and Katz used to find a near-optimal bound for the Erdős distinct distance problem Reference GK15.
There is now a wide variety of polynomial partitioning results. A lucid introduction to the subject can be found in Guth’s book Reference Gut16b. Such methods, and extensions of the cutting lemma, continue to be used successfully to prove results in incidence geometry Reference ST12Reference Zah15 and harmonic analysis Reference Gut16aReference DGL17Reference GHI19.
Another important theorem in discrete geometry is Rado’s centerpoint theorem Reference Rad46. For a finite set in we say that , is a centerpoint if every closed half-space that contains contains at least points of The existence of centerpoints follows from Helly’s theorem. They can be used as a high-dimensional analogue of a median, so their computation is an interesting problem .Reference Cha04.
A common generalization of the centerpoint theorem and the ham sandwich theorem was proved by Dolnikov Reference Dol92 and by Živaljević and Vrećica Reference ŽV90.
For this is the centerpoint theorem and for this is the ham sandwich theorem. A discrete variant of the theorem above, which simultaneously generalizes the ham sandwich theorem and Tverberg’s theorem, was conjectured by Tverberg and Vrećica Reference TV93. Tverberg’s theorem guarantees the existence of partitions of finite sets in into parts whose convex hulls intersect (see, e.g., Reference BZ17Reference BS18aReference DLGMM19 and the references therein.)
Finally, we can impose conditions on the transversals to the support of our measures. We say that a family of measures in is well-separated if for any two nonempty disjoint subsets the support of the measure , can be separated by a hyperplane from the support of the measures Bárány, Hubard, and Jerónimo proved that the ham sandwich theorem can be significantly strengthened for well-separated families of measures .Reference BHJ08.
The case was proved earlier by Steinhaus Reference Ste45.
3.4. Partitions of families of lines
There are different ways to extend the ham sandwich theorem to obtain a partition for families of lines. Given two nonparallel lines in the plane, consider We can arbitrarily assign distinct signs .( to the two rays from ) that form and the same for , Then, any other line . can be assigned one of four pairs depending on which rays of ) and it intersects. Langerman and Steiger proved that one can always use the assignment just described to obtain equipartitions of a single family of lines in the plane Reference LS03.
Other partitioning results have positive outcomes for several families of lines. Given a finite family of lines in no two of them parallel, and in a set , we can consider the size of , as
Note that is not a measure. Dujmović and Langerman proved a ham sandwich theorem for these functions Reference DL13.
The lower bounds on and are optimal in the result above.
An extension of the theorem above similar to Theorem 3.0.1 was proved by Xue and Soberón Reference XS19.
A key step in the proof by Langerman and Dujmović is the following, which is a consequence of the Erdős–Szekeres theorem on monotone sequences.
Theorem 3.4.2 extends to higher dimensions. The guarantee on the size of each half-space relies on geometric Ramsey-type results that have a much smaller rate of growth Reference CFP 14. An interesting question is whether Lemma 3.4.4 generalizes to a larger number of parts.
The following result follows from yet another interpretation for splitting lines in the plane Reference BHK 15.
The following new theorem improves the result above. Recall that there is a natural correspondence between the set of hyperplanes in and the punctured projective space Therefore, we may talk about absolutely continuous measures in the space of hyperplanes by using this bijection. .
Another way to split families of lines appears if we go one dimension higher. Given two nonvertical lines in that do not intersect but are not parallel, there is a unique vertical line that intersects both of them. We say that is above if is above Schnider showed that we can find a ham sandwich theorem for splitting several families of lines with a single additional line .Reference Sch20.
The partitioning line can be found in time for Reference PS19. If we let be the vertical plane that contains almost every line in , , , intersects at a single point, and is now a halving line for each of those sets. Therefore, the theorem above can be interpreted as an improvement of the ham sandwich theorem: if we are given the freedom to choose we can halve more colors than the usual ham sandwich theorem usually allows. Schnider’s result extends to halving families of , affine planes in -dimensional using a affine plane to split them. -dimensional
3.5. Partitions with restrictions on the pieces
Convex partitions of even restricted to generalized Voronoi diagrams, are very general. We can impose additional constraints on the possible shapes of the pieces. In contrast to the rest of the survey, this subsection’s main results are about types of partitions that can never split certain measures evenly. ,
Buck and Buck proved one of the first theorems of this type. They showed that it is impossible to split a convex body in into seven regions of equal area by three lines Reference BB49. Scott later generalized this to higher dimensions Reference Sco90.
The following problem was solved by Monsky Reference Mon70, answering a question of Fridman Reference Tho68.
The techniques used to prove this are surprising, as they seem at first glance far detached from this problem. The first tool is Sperner’s lemma Reference Spe28. Sperner’s lemma guarantees the existence of colorful simplices on certain colorings of triangulations of polytopes. It is a discrete version of the Knaster–Kuratowski–Mazuriewicz theorem Reference KKM29. The second is valuations of real numbers. For a prime number -adic the , valuation of a rational number -adic where are not divisible by is Such valuation can be extended to the real numbers. Monsky’s proof uses . Then, the points in the plane are divided into three (not convex!) sets .
The rest of the proof consists of showing that induce a KKM coloring on any triangulation of the square and that any triangle with one vertex in each of , cannot have area of the form for any odd integer .
We can obtain a different perspective on this solution by considering the function
A partition of the domain into three particular convex cones induces the partition of used in Monsky’s solution.
The theorem above can be improved upon. Kasimatis showed that if a regular is divided into triangles of equal area and -gon their number must be a multiple of , Reference Kas89. Similar results are known for broader families of polygons Reference Rud13.
A high-dimensional version says that a hypercube in cannot be partitioned into simplices of equal volume unless their number is a multiple of Reference Mea79Reference BN98. The proof of these results uses valuations for every prime -adic that divides .
If instead of triangles we use congruent convex pieces, the following problem remains open.
This has been answered affirmatively for Reference Mal94 and for Reference YZZ16.
4. More classes of partitions
4.1. Sets of fixed size
Most mass partition problems deal with ways to split measures into pieces of equal size. Often, this is a strict requirement on the problem. For example, it is easy to find pairs of probability measures in such that for any there exist no hyperplane that cuts simultaneously from both measures on one side and on the other.
For it may still be possible to find a single convex set of the same size under many measures.
The problem above is trivial for It has been solved positively for . with any by Blagojević and Dimitrijević Blagojević Reference BDB07 (see also Reference Bes03 for a proof for using fewer topological tools). For the discrete version of this problem, if we are given points of two different colors in the plane, there are algorithms that find a convex set with an of each color in -fraction time in general and in time when Reference AADB 18.
If is an integer, Akopyan and Karasev proved a stronger statement: there is a convex set of size for measures given in advance Reference AK13. For measures the condition on is necessary.
In dimension one, a classic result of Stromquist and Woodall solves the problem of finding a simple set of size in many measures simultaneously Reference SW85.
Another variant of Problem 2.1.1, posed by Grünbaum and made public by Bárány, concerns uneven partitions Reference KSSS10.
The answer to this problem is conjectured to be positive. This is true when the diameter of is at least times larger than the minimum width of Reference AJCMRP10. The question can also be asked for an absolutely continuous measure instead of a convex body. In this case, Bárány conjectures that the answer is negative.
Blagojević and Dimitrijević Blagojević proved the following version for the sphere Reference BDB13.
4.2. Partitions by fans and cones
In the plane, a ham sandwich cut of two measures is given by a line. Another simple shape we can use to make a partition is a consisting of -fan, rays emanating from a point. We call the parts wedges in such a partition. We distinguish convex where each of the -fans, resulting parts must be convex, from general that admit up to one nonconvex part. We admit degenerate cases, formed by a partition into -fans, sets by parallel line in the case of convex and a partition into -fans, sets by parallel lines (where the two extreme sections are part of the same set) for the nonconvex fans. Just as the space of half-planes can be parametrized with certain spaces of , lead us to interesting topological parametrizations. Given an absolutely continuous probability measure -fans in the plane, and positive real numbers that sum to one, the space of such that the wedges have measures -fans in clockwise order can be parametrized with SO If . a shift over the wedges induces a free action of , on this space.
We say that a family of measures in the plane can be by a -partitioned if there exists a -fan such that the -fan wedge has an th of each of the measures. -fraction
The known results for Problem 4.2.1 are summarized in Table 1. Algorithms to find of three point sets in -partitioning time were found by Bereg, where is the total number of points Reference Ber05. The existence of for two measures by Blagojević and Dimitrijević Blagojević -partitionsReference BDB07 implies a positive answer for Problem 4.1.1 in the plane. This is because at least one of the sections with size must be convex. Theorem 3.0.1 shows that, for fan partitions of two measures, we can also assume the fan is convex. Further results can be found in Reference BBDB12Reference VŽ03Reference BBS10.
Another variation concerning partitions by translates of fans in the plane was proved by Balitskiy, Garber, and Karasev Reference BGK15.
In high dimensions, there are two common ways to extend the notion of a fan. One is to look for partitions of formed by projecting to a two-dimensional subspace, finding a partition, and then taking the inverse image of each section under the projection. For these partitions, Makeev showed in 1994 that one can split -fan measures with a where -fan, is prime (see Reference Kar08, Thm. 57). A full proof was recently presented by Schnider Reference Sch19.
Bukh, Matoušek, and Nivasch proved that any finite absolutely continuous measure in can be split into equal parts using hyperplanes with a common affine plane -dimensionalReference BMN10. As an application of this result, they show that for any set of points in there exists a plane that intersects the convex hull of at least -dimensional triangles with vertices in .
Several results listed in Table 1 extend to Consider the case of . partitions by a For any -fan. measures in by the ham sandwich theorem we can find a hyperplane , halving every measure. If we apply the ham sandwich theorem again on one side of the partition, we find a hyperplane halving each measure in The intersection of these two hyperplanes is a . affine space. The set -dimensional forms a that shows a simultaneous -fan partition.
For the case of using -partitions we can also simultaneously split any -fans, measures in It suffices to apply Theorem .3.0.1 for Any partition of . into three convex sets is made by a -fan.
The second approach is to take a convex polytope surrounding the origin and consider the cones induced by the facets of the Formally, the cone partition induced by . is the partition formed by the family of sets
We also consider conical partitions that are not centered at the origin. As an example, consider an absolutely continuous probability measure in We want to know if there exists a regular hypercube . such that each of the cones it induces have the same measure. The case was first solved by Makeev Reference Mak88. If the measure is centrally symmetric around the origin and the hypercube we seek must also be centered at the origin, Karasev showed that such a cone partition exists for a power of a prime Reference Kar10bReference Kar10a.
If we fix a cone partition induced by a simplex whose interior contains the origin, any absolutely continuous probability measure in can be split into sets of prescribed size by a translate of this cone partition, as shown by Kuratowski and Steinhaus Reference KS53, extending earlier results by Levi Reference Lev30.
This theorem was also proved by Borsuk Reference Bor53, and later rediscovered by Vrećica and Živaljević Reference VŽ01Reference VŽ92. Vrećica and Živaljević’s approach extends to partitions into parts of prescribed sizes, with parts of the form
for some and see Figure ;7. A discrete version of Theorem 4.2.3 in the plane was proved by Bose et al. Reference BGL 97 in order to solve an illumination problem. The translated fan they use to split a set of points does not have to be a convex fan, as in Kuratowski and Steinhaus’s theorem. Moreover, their method yields an algorithm that splits a set of points into three families of prescribed size in time.
A simple proof of Theorem 4.2.3 with modern techniques follows from the results of Aurenhammer, Hoffmann, and Aronov Reference AHA98 mentioned in Section 3. It suffices to apply the main theorem of Reference AHA98 to a power diagram with sites (the polar of the hyperplane containing for ) To obtain the extension of Vrećica and Živaljević, just include an additional site at . It is easy to show that the partitions induced by these power diagrams are among those considered in Theorem .4.2.3.
A result very similar to Kuratowski and Steinhaus’s theorem was proved by Numata and Tokuyama Reference NT93.
We can recover a discrete version of Theorem 4.2.3 from this theorem by using limits involving increasingly larger homothetic simplices. Numata and Tokuyama also give algorithms to find in time or in time if is considered as a constant.
Cone partitioning problems allow for an approach with Fourier analysis if the cones are made with the facets of a polytope that is invariant under a representation of a finite group Reference Sim15. Another extension of cone partitions, called polyhedral curtains, is presented by Živaljević to prove yet another generalization of the ham sandwich theorem Reference Živ15.
4.3. Partitions with curves of bounded complexity
In addition to hyperplanes, other algebraic surfaces can be used to make a partition. Perhaps the best-known result of this kind is the Stone–Tukey theorem Reference ST42.
The proof involves the use of a standard Veronese map where the , of the image corresponds to the evaluation of the -coordinate nontrivial monomial of degree at most th on variables. The inverse image of a half-space in the higher-dimensional space corresponds to a set such as or in Therefore, as in the proof we present of the ham sandwich theorem, the space of sets of the form . can be parametrized by a high-dimensional sphere, and an application of the Borsuk–Ulam theorem finishes the proof. Stone and Tukey observed that much more could be obtained using that same idea. As an example, consider the following corollary.
The case was proved by Steinhaus independently Reference Ste45. The polynomial partitioning theorem (Theorem 3.3.6) stands out as an important application of the Stone–Tukey theorem.
Another consequence of the proof method described above is that any measures in the plane can be simultaneously halved by the graph of a polynomial of degree Instead of polynomials, we may want to use paths that can only use vertical or horizontal segments. The following conjecture by Mikio Kano remains open. .
The conjecture above has been solved for Reference UKK09. If the horizontal portions of the paths are allowed to go through infinity, then the conjecture is known to hold Reference KRPS16. Theorem 4.2.2 implies the case of Conjecture 4.3.3 by taking a fan made by the union of a vertical line and a horizontal line. Figure 8 shows that we must consider self-intersecting paths for Conjecture 4.3.3 to be true.
5. Extremal variants
In the ham sandwich theorem, the halving hyperplane is sometimes unique. For example, if each of the measures is uniformly distributed in a certain sphere, a halving hyperplane must contain all the spheres’ centers.
If we reduce the number of measures, we expect to have significantly more halving hyperplanes. This leads to extremal versions of ham sandwich problems. We could be interested in counting halving hyperplanes, or finding halving hyperplanes with additional conditions. Even the case of a single measure is interesting.
Consider the case when we are given a measure whose support is contained in a polygonal region which is not necessarily convex. We can look for a segment between points in the boundary of , that divides as evenly as possible. It is possible that no chord of this type halves exactly. We can also look for a broken line, formed by segments contained in that halves , There are algorithms that find the shortest halving broken line .Reference BDH 07.
If we aim to split a fraction greater than some constant on each side with a single segment in there are algorithms that compute the shortest chord possible ,Reference BCK 98. The running time depends on the number of segments in the boundary of and the complexity of The maximum value . we can obtain depends on whether we want one of the chord’s endpoints to be a vertex of .
If the support of is a polygon we can also obtain algorithms for some continuous ham sandwich theorems. These include halving lines of the area of two convex polygons or halving planes of the volume of three convex polyhedra ,Reference She92Reference Sto91. The algorithms depend on the number of vertices of the supports. These problems are closely related to a broader class of problems known as polygonal cutting Reference KS85.
5.1. Halving hyperplanes
Given a finite set of points in general position in we say that a hyperplane is a halving hyperplane if it cuts the set exactly in half. We allow the hyperplane to contain a point of , if is odd. The ham sandwich theorem says that any finite sets in share a halving hyperplane, which intuitively tells us that any finite set must have a large family of halving hyperplanes. The question of counting the number of halving hyperplanes becomes relevant. We say that two halving hyperplanes and of a set are equivalent if they split into the same pair of subsets.
In the problem of counting halving planes was the original motivation for studying the colorful variations of Tverberg’s theorem ,Reference BFL90. This gave an bound on the number of halving planes for a set of points. The same technique gave an bound in Reference ŽV92Reference ABFK92. The best lower bound is due to Tóth, who constructed sets with halving hyperplanes Reference Tót01. Nivash proved similar bounds for the plane but with a larger constant in the exponent Reference Niv08. Several improvements in dimension three have pushed the upper bound down to Reference SST01 and to in dimension four Reference Sha11. In dimension two, the current best bound of halving lines is due to Dey Reference Dey98. A long-standing conjecture on the number of halving lines in the plane as made by Erdős, Lovász, Simmons, and Strausz Reference ELSS73.
Additional structure on the set of points can help us improve the bounds on halving hyperplanes. One such condition is . A set of points in -density is if the ratio between the largest distance and the shortest distance does not exceed -dense For . sets of -dense points in the plane, the number of halving lines is bounded by In dimension . the number of halving hyperplanes of a dense set is at most , Reference EVW97. The current lower bound for the number of halving hyperplanes for a dense family of points matches those for points in general Reference KT19. Improved bounds on the number of halving planes also exist for random sets of points Reference BS94.
Many of the results above extend to counting which are relevant in many problems in computational geometry -sets,Reference CSY84. Given a finite set a , -set is a set such that and (alternatively, a hyperplane separates and ).
For example, the bound by Sharir, Smorodinsky, and Tardos on halving planes in follows from a bound of on the number of in -sets For precise statements, we recommend Wagner’s comprehensive survey on . and their applications -setsReference Wag08.
The number of of planar sets is closely related to the rectilinear crossing number of complete graphs. Crossing numbers escape the scope of this survey, but the interested reader can learn about this connection in the survey by Ábrego, Fernández-Merchant, and Salazar -setsReference ÁFMS12. The number of halving planes of a set in is also related to the planar problem of finding points covered by many triangles with vertices in a given set of points Reference ACE 91.
5.2. The same-type lemma
Given two -tuples and of points in we are interested in whether they are combinatorially equivalent or not. We say they have the same type if each pair of simplices , and have the same orientation. The orientation of the simplex can be defined as the sign of the determinant of the matrix where the column is th .
A repeated application of the ham sandwich theorem was used by Bárány and Valtr to prove the following theorem Reference BV98.
The best bound for the constant is by Fox, Pach, and Suk Reference FPS16. The main result of Fox, Pach, and Suk (a regularity lemma for semialgebraic hypergraphs) is much more general. One of the key points in their proof is an application of another mass partitioning theorem by Chazelle Reference Cha93 in the vein of Theorem 3.3.5. A much more general result regarding partitions of a set of points in into convex clusters was proved by Pór and Valtr Reference PV02.
Acknowledgments
The authors thank Jesús de Loera, Ruy Fábila, Gabriel Nivasch, Florian Frick, Peter Landweber, Luis Montejano, Dömötör Pálvölgyi, Adam Sheffer, Jorge Urrutia, and the anonymous referee for their comments. We also thank Peter Winkler and Arseniy Akopyan for pointing out Example 2.4.4 and the reference to its origin.
About the authors
Edgardo Roldán-Pensado is associate professor of mathematics at the National Autonomous University of Mexico. His research is mainly focused on convex and discrete geometry.
Pablo Soberón is assistant professor at Baruch College, City University of New York. His research focuses on discrete geometry and topological combinatorics.