A survey of mass partitions

Roldán-Pensado, Edgardo; Soberón, Pablo

doi:10.1090/bull/1725

A survey of mass partitions
HTML articles powered by AMS MathViewer

by Edgardo Roldán-Pensado and Pablo Soberón;

Bull. Amer. Math. Soc. 59 (2022), 227-267

DOI: https://doi.org/10.1090/bull/1725

Published electronically: February 24, 2021

HTML | PDF | Request permission

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.

References

J. Akiyama and N. Alon, Disjoint simplices and geometric hypergraphs, Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985) Ann. New York Acad. Sci., vol. 555, New York Acad. Sci., New York, 1989, pp. 1–3. MR 1018601, DOI 10.1111/j.1749-6632.1989.tb22429.x
Oswin Aichholzer, Nieves Atienza, José M. Díaz-Báñez, Ruy Fabila-Monroy, David Flores-Peñaloza, Pablo Pérez-Lantero, Birgit Vogtenhuber, and Jorge Urrutia, Computing balanced islands in two colored point sets in the plane, Inform. Process. Lett. 135 (2018), 28–32. MR 3779971, DOI 10.1016/j.ipl.2018.02.008
A. Akopyan, S. Avvakumov, and R. N. Karasev, Convex fair partitions into an arbitrary number of pieces, arXiv:1804.03057 (2018).
Timothy G. Abbott, Michael A. Burr, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, John Hugg, Daniel Kane, Stefan Langerman, Jelani Nelson, Eynat Rafalin, Kathryn Seyboth, and Vincent Yeung, Dynamic ham-sandwich cuts in the plane, Comput. Geom. 42 (2009), no. 5, 419–428. MR 2512670, DOI 10.1016/j.comgeo.2008.09.008
Noga Alon, Imre Bárány, Zoltán Füredi, and Daniel J. Kleitman, Point selections and weak $\epsilon$-nets for convex hulls, Combin. Probab. Comput. 1 (1992), no. 3, 189–200. MR 1208800, DOI 10.1017/S0963548300000225
Boris Aronov, Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, and Rephael Wenger, Points and triangles in the plane and halving planes in space, Discrete Comput. Geom. 6 (1991), no. 5, 435–442. MR 1115101, DOI 10.1007/BF02574700
Bogdan Armaselu and Ovidiu Daescu, Algorithms for fair partitioning of convex polygons. part 3, Theoret. Comput. Sci. 607 (2015), no. part 3, 351–362. MR 3429058, DOI 10.1016/j.tcs.2015.08.003
Pankaj K. Agarwal and Jeff Erickson, Geometric range searching and its relatives, Advances in discrete and computational geometry (South Hadley, MA, 1996) Contemp. Math., vol. 223, Amer. Math. Soc., Providence, RI, 1999, pp. 1–56. MR 1661376, DOI 10.1090/conm/223/03131
Bernardo M. Ábrego, Silvia Fernández-Merchant, and Gelasio Salazar, The rectilinear crossing number of $K_n$: closing in (or are we?), Thirty essays on geometric graph theory, Springer, New York, 2013, pp. 5–18. MR 3205146, DOI 10.1007/978-1-4614-0110-0_{2}
Megumi Asada, Florian Frick, Vivek Pisharody, Maxwell Polevy, David Stoner, Ling Hei Tsang, and Zoe Wellner, Fair division and generalizations of Sperner- and KKM-type results, SIAM J. Discrete Math. 32 (2018), no. 1, 591–610. MR 3769696, DOI 10.1137/17M1116210
N. Alon and A. Graur, Efficient splitting of measures and necklaces, arXiv:2006.16613 (2020).
Noga Alon, Jarosław Grytczuk, MichałLasoń, and Mateusz Michałek, Splitting necklaces and measurable colorings of the real line, Proc. Amer. Math. Soc. 137 (2009), no. 5, 1593–1599. MR 2470817, DOI 10.1090/S0002-9939-08-09699-8
F. Aurenhammer, F. Hoffmann, and B. Aronov, Minkowski-type theorems and least-squares clustering, Algorithmica 20 (1998), no. 1, 61–76. MR 1483422, DOI 10.1007/PL00009187
J. Arocha, J. Jerónimo-Castro, L. Montejano, and E. Roldán-Pensado, On a conjecture of Grünbaum concerning partitions of convex sets, Period. Math. Hungar. 60 (2010), no. 1, 41–47. MR 2629653, DOI 10.1007/s10998-010-1041-7
Arseniy Akopyan and Roman Karasev, Cutting the same fraction of several measures, Discrete Comput. Geom. 49 (2013), no. 2, 402–410. MR 3017919, DOI 10.1007/s00454-012-9450-4
S. Avvakumov and R. Karasev, Equipartition of a segment, arXiv:2009.09862 (2020).
J. Akiyama, A. Kaneko, M. Kano, G. Nakamura, E. Rivera-Campo, S. Tokunaga, and J. Urrutia, Radial perfect partitions of convex sets in the plane, Discrete and computational geometry (Tokyo, 1998) Lecture Notes in Comput. Sci., vol. 1763, Springer, Berlin, 2000, pp. 1–13. MR 1787512, DOI 10.1007/978-3-540-46515-7_{1}
Noga Alon, Splitting necklaces, Adv. in Math. 63 (1987), no. 3, 247–253. MR 877785, DOI 10.1016/0001-8708(87)90055-7
J. Akiyama, G. Nakamura, E. Rivera-Campo, and J. Urrutia, Perfect divisions of a cake, Proceedings of the 10th Canadian Conference on Computational Geometry (CCCG’98), 1998.
David Avis, Nonpartitionable point sets, Inform. Process. Lett. 19 (1984), no. 3, 125–129. MR 782220, DOI 10.1016/0020-0190(84)90090-5
Noga Alon and Douglas B. West, The Borsuk-Ulam theorem and bisection of necklaces, Proc. Amer. Math. Soc. 98 (1986), no. 4, 623–628. MR 861764, DOI 10.1090/S0002-9939-1986-0861764-9
Julius B. Barbanel, The geometry of efficient fair division, Cambridge University Press, Cambridge, 2005. With an introduction by Alan D. Taylor. MR 2132232, DOI 10.1017/CBO9780511546679
R. C. Buck and Ellen F. Buck, Equipartition of convex sets, Math. Mag. 22 (1949), 195–198. MR 29521, DOI 10.2307/3029182
Imre Bárány, Pavle Blagojević, and Aleksandra Dimitrijević Blagojević, Functions, measures, and equipartitioning convex $k$-fans, Discrete Comput. Geom. 49 (2013), no. 2, 382–401. MR 3017918, DOI 10.1007/s00454-012-9467-8
Sergey Bereg, Prosenjit Bose, and David Kirkpatrick, Equitable subdivisions within polygonal regions, Comput. Geom. 34 (2006), no. 1, 20–27. MR 2205944, DOI 10.1016/j.comgeo.2005.06.003
P. V. M. Blagojević, A. D. Blagojević, and R. N. Karasev, More bisections by hyperplane arrangements, arXiv:1809.05364 (2018).
Imre Bárány, Pavle Blagojević, and András Szűcs, Equipartitioning by a convex 3-fan, Adv. Math. 223 (2010), no. 2, 579–593. MR 2565542, DOI 10.1016/j.aim.2009.08.016
P. Bose, J. Czyzowicz, E. Kranakis, D. Krizanc, and A. Maheshwari, Polygon cutting: Revisited, Discrete and Computational Geometry, Springer, Berlin, Heidelberg, Berlin, Heidelberg, December 1998, pp. 81–92.
I. Bogdanov, G. Chelnokov, and E. Kulikov, Problem 4. robbers sharing boxed loot, https://www.turgor.ru/lktg/2005/4/index.htm, 2005, 17th Tournament of Towns Summer Conference.
Pavle V. M. Blagojević and Aleksandra S. Dimitrijević Blagojević, Using equivariant obstruction theory in combinatorial geometry, Topology Appl. 154 (2007), no. 14, 2635–2655. MR 2340948, DOI 10.1016/j.topol.2007.04.007
Pavle V. M. Blagojević and Aleksandra Dimitrijević Blagojević, A problem related to Bárány-Grünbaum conjecture, Filomat 27 (2013), no. 1, 109–113. MR 3243905, DOI 10.2298/FIL1301109B
Prosenjit Bose, Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, and Pat Morin, Geodesic ham-sandwich cuts, Discrete Comput. Geom. 37 (2007), no. 3, 325–339. MR 2301521, DOI 10.1007/s00454-006-1287-2
Sergey Bereg, Equipartitions of measures by 2-fans, Discrete Comput. Geom. 34 (2005), no. 1, 87–96. MR 2140884, DOI 10.1007/s00454-004-1151-1
Sergey Bereg, Computing generalized ham-sandwich cuts, Inform. Process. Lett. 112 (2012), no. 13, 532–534. MR 2921592, DOI 10.1016/j.ipl.2012.03.013
Sergei Bespamyatnikh, On partitioning a cake, Discrete and computational geometry, Lecture Notes in Comput. Sci., vol. 2866, Springer, Berlin, 2003, pp. 60–71. MR 2097252, DOI 10.1007/978-3-540-44400-8_{7}
Pavle V. M. Blagojević, Florian Frick, Albert Haase, and Günter M. Ziegler, Hyperplane mass partitions via relative equivariant obstruction theory, Doc. Math. 21 (2016), 735–771. MR 3548132
Pavle V. M. Blagojević, Florian Frick, Albert Haase, and Günter M. Ziegler, Topology of the Grünbaum-Hadwiger-Ramos hyperplane mass partition problem, Trans. Amer. Math. Soc. 370 (2018), no. 10, 6795–6824. MR 3841833, DOI 10.1090/tran/7528
I. Bárány, Z. Füredi, and L. Lovász, On the number of halving planes, Combinatorica 10 (1990), no. 2, 175–183. MR 1082647, DOI 10.1007/BF02123008
Alexey Balitskiy, Alexey Garber, and Roman Karasev, Another ham sandwich in the plane, Ann. Comb. 19 (2015), no. 2, 235–242. MR 3347381, DOI 10.1007/s00026-015-0270-0
Prosenjit Bose, Leonidas Guibas, Anna Lubiw, Mark Overmars, Diane Souvaine, and Jorge Urrutia, The floodlight problem, Internat. J. Comput. Geom. Appl. 7 (1997), no. 1-2, 153–163. Workshop on Computational Geometry (Raleigh, NC, 1993). MR 1446536, DOI 10.1142/S0218195997000090
Imre Bárány, Alfredo Hubard, and Jesús Jerónimo, Slicing convex sets and measures by a hyperplane, Discrete Comput. Geom. 39 (2008), no. 1-3, 67–75. MR 2383751, DOI 10.1007/s00454-007-9021-2
Sergey Bereg, Ferran Hurtado, Mikio Kano, Matias Korman, Dolores Lara, Carlos Seara, Rodrigo I. Silveira, Jorge Urrutia, and Kevin Verbeek, Balanced partitions of 3-colored geometric sets in the plane, Discrete Appl. Math. 181 (2015), 21–32. MR 3284508, DOI 10.1016/j.dam.2014.10.015
S. Bespamyatnikh, D. Kirkpatrick, and J. Snoeyink, Generalizing ham sandwich cuts to equitable subdivisions, Discrete Comput. Geom. 24 (2000), no. 4, 605–622. ACM Symposium on Computational Geometry (Miami, FL, 1999). MR 1799604, DOI 10.1145/304893.304909
Prosenjit Bose and Stefan Langerman, Weighted ham-sandwich cuts, Discrete and computational geometry, Lecture Notes in Comput. Sci., vol. 3742, Springer, Berlin, 2005, pp. 48–53. MR 2212093, DOI 10.1007/11589440_{5}
I. Bárány and J. Matoušek, Simultaneous partitions of measures by $k$-fans, Discrete Comput. Geom. 25 (2001), no. 3, 317–334. MR 1815435, DOI 10.1007/s00454-001-0003-5
I. Bárány and J. Matoušek, Equipartition of two measures by a 4-fan, Discrete Comput. Geom. 27 (2002), no. 3, 293–301. MR 1921557, DOI 10.1007/s00454-001-0071-6
Boris Bukh, Jiří Matoušek, and Gabriel Nivasch, Stabbing simplices by points and flats, Discrete Comput. Geom. 43 (2010), no. 2, 321–338. MR 2579699, DOI 10.1007/s00454-008-9124-4
Boris M. Bekker and Nikita Yu. Netsvetaev, Generalized Sperner lemma and subdivisions into simplices of equal volume, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 231 (1995), no. Issled. po Topol. 8, 245–254, 327 (1996) (English, with Russian summary); English transl., J. Math. Sci. (New York) 91 (1998), no. 6, 3492–3498. MR 1434297, DOI 10.1007/BF02434927
K. Borsuk, An application of the theorem on antipodes to the measure theory, Bull. Acad. Polon. Sci. Cl. III. 1 (1953), 87–90. MR 57304
L. Barba, A. Pilz, and P. Schnider, Sharing a pizza: bisecting masses with two cuts, arXiv:1904.02502 (2019).
Pavle V. M. Blagojević, Nevena Palić, Pablo Soberón, and Günter M. Ziegler, Cutting a part from many measures, Forum Math. Sigma 7 (2019), Paper No. e37, 34. MR 4024935, DOI 10.1017/fms.2019.33
Pavle V. M. Blagojević, Günter Rote, Johanna K. Steinmeyer, and Günter M. Ziegler, Convex equipartitions of colored point sets, Discrete Comput. Geom. 61 (2019), no. 2, 355–363. MR 3903793, DOI 10.1007/s00454-017-9959-7
Imre Bárány and William Steiger, On the expected number of $k$-sets, Discrete Comput. Geom. 11 (1994), no. 3, 243–263. MR 1271635, DOI 10.1007/BF02574008
Imre Bárány and Pablo Soberón, Tverberg’s theorem is 50 years old: a survey, Bull. Amer. Math. Soc. (N.S.) 55 (2018), no. 4, 459–492. MR 3854075, DOI 10.1090/bull/1634
Pavle V. M. Blagojević and Pablo Soberón, Thieves can make sandwiches, Bull. Lond. Math. Soc. 50 (2018), no. 1, 108–123. MR 3778548, DOI 10.1112/blms.12109
Steven J. Brams and Alan D. Taylor, Fair division, Cambridge University Press, Cambridge, 1996. From cake-cutting to dispute resolution. MR 1381896, DOI 10.1017/CBO9780511598975
I. Bárány and P. Valtr, A positive fraction Erdős-Szekeres theorem, Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 335–342. Dedicated to the memory of Paul Erdős. MR 1608874, DOI 10.1007/PL00009350
Pavle V. M. Blagojević and Günter M. Ziegler, Convex equipartitions via equivariant obstruction theory, Israel J. Math. 200 (2014), no. 1, 49–77. MR 3219570, DOI 10.1007/s11856-014-1006-6
Pavle V. M. Blagojević and Günter M. Ziegler, Beyond the Borsuk-Ulam theorem: the topological Tverberg story, A journey through discrete mathematics, Springer, Cham, 2017, pp. 273–341. MR 3726602
W. A. Beyer and Andrew Zardecki, The early history of the ham sandwich theorem, Amer. Math. Monthly 111 (2004), no. 1, 58–61. MR 2026317, DOI 10.2307/4145019
Yu Hin Chan, Shujian Chen, Florian Frick, and J. Tristan Hull, Borsuk-Ulam theorems for products of spheres and Stiefel manifolds revisited, Topol. Methods Nonlinear Anal. 55 (2020), no. 2, 553–564. MR 4131166, DOI 10.12775/tmna.2019.103
Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, and Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (1990), no. 2, 99–160. MR 1032370, DOI 10.1007/BF02187783
B. Chazelle and J. Friedman, A deterministic view of random sampling and its use in geometry, Combinatorica 10 (1990), no. 3, 229–249. MR 1092541, DOI 10.1007/BF02122778
David Conlon, Jacob Fox, János Pach, Benny Sudakov, and Andrew Suk, Ramsey-type results for semi-algebraic relations, Trans. Amer. Math. Soc. 366 (2014), no. 9, 5043–5065. MR 3217709, DOI 10.1090/S0002-9947-2014-06179-5
Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete Comput. Geom. 9 (1993), no. 2, 145–158. MR 1194032, DOI 10.1007/BF02189314
Timothy M. Chan, An optimal randomized algorithm for maximum Tukey depth, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2004, pp. 430–436. MR 2291081
G. W. Cox and R. D. McKelvey, A ham sandwich theorem for general measures, Social Choice and Welfare 1 (1984), no. 1, 75–83.
Richard Courant and Herbert Robbins, What Is Mathematics?, Oxford University Press, New York, 1941. MR 5358
R. Cole, M. Sharir, and C.-K. Yap, On k-hulls and related problems, Symposium on Theory of Computing, 1984, pp. 154–166.
T. K. Dey, Improved bounds for planar $k$-sets and related problems, Discrete Comput. Geom. 19 (1998), no. 3, Special Issue, 373–382. Dedicated to the memory of Paul Erdős. MR 1608878, DOI 10.1007/PL00009354
Xiumin Du, Larry Guth, and Xiaochun Li, A sharp Schrödinger maximal estimate in $\Bbb R^2$, Ann. of Math. (2) 186 (2017), no. 2, 607–640. MR 3702674, DOI 10.4007/annals.2017.186.2.5
Vida Dujmović and Stefan Langerman, A center transversal theorem for hyperplanes and applications to graph drawing, Discrete Comput. Geom. 49 (2013), no. 1, 74–88. MR 3010218, DOI 10.1007/s00454-012-9464-y
Jesús A. De Loera, Xavier Goaoc, Frédéric Meunier, and Nabil H. Mustafa, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Bull. Amer. Math. Soc. (N.S.) 56 (2019), no. 3, 415–511. MR 3974609, DOI 10.1090/bull/1653
Mark de Longueville and Rade T. Živaljević, Splitting multidimensional necklaces, Adv. Math. 218 (2008), no. 3, 926–939. MR 2414326, DOI 10.1016/j.aim.2008.02.003
Albrecht Dold, Simple proofs of some Borsuk-Ulam results, Proceedings of the Northwestern Homotopy Theory Conference (Evanston, Ill., 1982) Contemp. Math., vol. 19, Amer. Math. Soc., Providence, RI, 1983, pp. 65–69. MR 711043, DOI 10.1090/conm/019/711043
V. L. Dol′nikov, A generalization of the sandwich theorem, Mat. Zametki 52 (1992), no. 2, 27–37, 155 (Russian, with Russian summary); English transl., Math. Notes 52 (1992), no. 1-2, 771–779 (1993). MR 1187871, DOI 10.1007/BF01236771
Herbert Edelsbrunner, Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Berlin, 1987. MR 904271, DOI 10.1007/978-3-642-61568-9
P. Erdős, L. Lovász, A. Simmons, and E. G. Straus, Dissection graphs of planar point sets, A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) North-Holland, Amsterdam-London, 1973, pp. 139–149. MR 363986
H. Edelsbrunner, P. Valtr, and E. Welzl, Cutting dense point sets in half, Discrete Comput. Geom. 17 (1997), no. 3, 243–255. MR 1432062, DOI 10.1007/PL00009291
Edward Fadell and Sufian Husseini, An ideal-valued cohomological index theory with applications to Borsuk-Ulam and Bourgin-Yang theorems, Ergodic Theory Dynam. Systems 8$^*$ (1988), no. Charles Conley Memorial Issue, 73–85. MR 967630, DOI 10.1017/S0143385700009342
M. Fradelizi, A. Hubard, M. Meyer, E. Roldán-Pensado, and A. Zvavitch, Equipartitions and Mahler volumes of symmetric convex bodies, arXiv:1904.10765 (2019).
Augustin Fruchard and Alexander Magazinov, Fair partitioning by straight lines, Convexity and discrete geometry including graph theory, Springer Proc. Math. Stat., vol. 148, Springer, [Cham], 2016, pp. 161–165. MR 3516708, DOI 10.1007/978-3-319-28186-5_{1}4
Jacob Fox, János Pach, and Andrew Suk, A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing, SIAM J. Comput. 45 (2016), no. 6, 2199–2223. MR 3585030, DOI 10.1137/15M1007355
A. Filos-Ratsikas, A. Hollender, K. Sotiraki, and M. Zampetakis, A topological characterization of modulo-p arguments and implications for necklace splitting, arXiv:2003.11974 (2020).
Aris Filos-Ratsikas and Paul W. Goldberg, The complexity of splitting necklaces and bisecting ham sandwiches, STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2019, pp. 638–649. MR 4003371, DOI 10.1145/3313276.3316334
Larry Guth, Jonathan Hickman, and Marina Iliopoulou, Sharp estimates for oscillatory integral operators via polynomial partitioning, Acta Math. 223 (2019), no. 2, 251–376. MR 4047925, DOI 10.4310/acta.2019.v223.n2.a2
Larry Guth and Nets Hawk Katz, On the Erdős distinct distances problem in the plane, Ann. of Math. (2) 181 (2015), no. 1, 155–190. MR 3272924, DOI 10.4007/annals.2015.181.1.2
M. Göös, P. Kamath, K, Sotiraki, and M. Zampetakis, On the complexity of modulo-q arguments and the Chevalley-warning theorem, arXiv:1912.04467 (2019).
M. Gromov, Isoperimetry of waists and concentration of maps, Geom. Funct. Anal. 13 (2003), no. 1, 178–215. MR 1978494, DOI 10.1007/s000390300004
B. Grünbaum, Partitions of mass-distributions and of convex bodies by hyperplanes, Pacific J. Math. 10 (1960), 1257–1261. MR 124818, DOI 10.2140/pjm.1960.10.1257
Larry Guth, A restriction estimate using polynomial partitioning, J. Amer. Math. Soc. 29 (2016), no. 2, 371–413. MR 3454378, DOI 10.1090/jams827
Larry Guth, Polynomial methods in combinatorics, University Lecture Series, vol. 64, American Mathematical Society, Providence, RI, 2016. MR 3495952, DOI 10.1090/ulect/064
Charles H. Goldberg and Douglas B. West, Bisection of circle colorings, SIAM J. Algebraic Discrete Methods 6 (1985), no. 1, 93–106. MR 772181, DOI 10.1137/0606010
H. Hadwiger, Simultane Vierteilung zweier Körper, Arch. Math. (Basel) 17 (1966), 274–278 (German). MR 199791, DOI 10.1007/BF01899586
Alfredo Hubard and Roman Karasev, Bisecting measures with hyperplane arrangements, Math. Proc. Cambridge Philos. Soc. 169 (2020), no. 3, 639–647. MR 4170619, DOI 10.1017/s0305004119000380
Andreas F. Holmsen, Jan Kynčl, and Claudiu Valculescu, Near equipartitions of colored point sets, Comput. Geom. 65 (2017), 35–42. MR 3670172, DOI 10.1016/j.comgeo.2017.05.001
A. Hollender, The classes PPA-k: Existence from arguments modulo k, International Conference on Web and Internet Economics, Springer, 2019, pp. 214–227.
Charles R. Hobby and John R. Rice, A moment problem in $L_{1}$ approximation, Proc. Amer. Math. Soc. 16 (1965), 665–670. MR 178292, DOI 10.1090/S0002-9939-1965-0178292-5
M. Humphreys, Can compactness constrain the Gerrymander?, Irish Political Studies 26 (2011), no. 4, 513–520.
David Haussler and Emo Welzl, $\epsilon$-nets and simplex range queries, Discrete Comput. Geom. 2 (1987), no. 2, 127–151. MR 884223, DOI 10.1007/BF02187876
Hiroshi Iriyeh and Masataka Shibata, Symmetric Mahler’s conjecture for the volume product in the $3$-dimensional case, Duke Math. J. 169 (2020), no. 6, 1077–1134. MR 4085078, DOI 10.1215/00127094-2019-0072
Hiro Ito, Hideyuki Uehara, and Mitsuo Yokoyama, 2-dimension ham sandwich theorem for partitioning into three convex pieces, Discrete and computational geometry (Tokyo, 1998) Lecture Notes in Comput. Sci., vol. 1763, Springer, Berlin, 2000, pp. 129–157. MR 1787521, DOI 10.1007/978-3-540-46515-7_{1}1
D. Jojić, G. Panina, and R. T. Živaljević, Splitting necklaces, with constraints, Oberwolfach Preprints OWP-2020-03 (2020).
R. N. Karasëv, Topological methods in combinatorial geometry, Uspekhi Mat. Nauk 63 (2008), no. 6(384), 39–90 (Russian, with Russian summary); English transl., Russian Math. Surveys 63 (2008), no. 6, 1031–1078. MR 2492772, DOI 10.1070/RM2008v063n06ABEH004578
R. N. Karasev, Equipartition of a measure by $(Z_p)^k$-invariant fans, Discrete Comput. Geom. 43 (2010), no. 2, 477–481. MR 2579709, DOI 10.1007/s00454-009-9138-6
R. N. Karasev, Knaster’s problem for $(Z_2)^k$-symmetric subsets of the sphere $S^{2^k-1}$, Discrete Comput. Geom. 44 (2010), no. 2, 429–438. MR 2671016, DOI 10.1007/s00454-009-9215-x
E. A. Kasimatis, Dissections of regular polygons into triangles of equal areas, Discrete Comput. Geom. 4 (1989), no. 4, 375–381. MR 996770, DOI 10.1007/BF02187738
S. Karthik C. and Arpan Saha, Ham sandwich is equivalent to Borsuk-Ulam, 33rd International Symposium on Computational Geometry (SoCG 2017) (Dagstuhl, Germany) (Boris Aronov and Matthew J. Katz, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 77, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017, pp. 24:1–24:15.
Roman Karasev, Alfredo Hubard, and Boris Aronov, Convex equipartitions: the spicy chicken theorem, Geom. Dedicata 170 (2014), 263–279. MR 3199487, DOI 10.1007/s10711-013-9879-5
Atsushi Kaneko and M. Kano, Discrete geometry on red and blue points in the plane—a survey, Discrete and computational geometry, Algorithms Combin., vol. 25, Springer, Berlin, 2003, pp. 551–570. MR 2038491, DOI 10.1007/978-3-642-55566-4_{2}5
Mikio Kano and Jan Kynčl, The hamburger theorem, Comput. Geom. 68 (2018), 167–173. MR 3715050, DOI 10.1016/j.comgeo.2017.06.012
B. Knaster, C. Kuratowski, and S. Mazurkiewicz, Ein Beweis des Fixpunktsatzes für n-dimensionale Simplexe, Fundamenta Mathematicae 14 (1929), no. 1, 132–137.
B. Knudsen, Configuration spaces in algebraic topology, arXiv:1803.11165 (2018).
Roman N. Karasev, Edgardo Roldán-Pensado, and Pablo Soberón, Measure partitions using hyperplanes with fixed directions, Israel J. Math. 212 (2016), no. 2, 705–728. MR 3505400, DOI 10.1007/s11856-016-1303-z
K. Kuratowski and H. Steinhaus, Une application géométrique du théorème de Brouwer sur les points invariants, Bull. Acad. Polon. Sci. Cl. III. 1 (1953), 83–86 (French). MR 58201
J. M. Keil and J.-R. Sack, Minimum decompositions of polygonal objects, Computational Geometry, Elsevier, 1985, pp. 197–216.
G. O. H. Katona, A. Schrijver, T. Szőnyi, and G. Sági (eds.), Open problems, pp. 355–365, Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.
István Kovács and Géza Tóth, Dense point sets with many halving lines, Discrete Comput. Geom. 64 (2020), no. 3, 965–984. MR 4156254, DOI 10.1007/s00454-019-00080-3
M. Kano and J. Urrutia, Discrete geometry on red and blue points in the plane—a survey, Graphs and Combinatorics (2020), 1–53.
MichałLasoń, Obstacles for splitting multidimensional necklaces, Proc. Amer. Math. Soc. 143 (2015), no. 11, 4655–4668. MR 3391025, DOI 10.1090/S0002-9939-2015-12611-1
Joseph Lehec, On the Yao-Yao partition theorem, Arch. Math. (Basel) 92 (2009), no. 4, 366–376. MR 2501292, DOI 10.1007/s00013-009-3013-9
Friedrich Levi, Die Drittelungskurve, Math. Z. 31 (1930), no. 1, 339–345 (German). MR 1545116, DOI 10.1007/BF01246415
Chi-Yuan Lo, J. Matoušek, and W. Steiger, Algorithms for ham-sandwich cuts, Discrete Comput. Geom. 11 (1994), no. 4, 433–452. MR 1273227, DOI 10.1007/BF02574017
S. Langerman and W. Steiger, Optimization in arrangements, STACS 2003, Springer, Berlin, Heidelberg, Berlin, Heidelberg, February 2003, pp. 50–61.
E. León and G. M. Ziegler, Spaces of convex n-partitions, New Trends in Intuitive Geometry, Springer Berlin Heidelberg, Berlin, Heidelberg, 2018, pp. 279–306.
V. V. Makeev, Partitioning space in six parts, Vestn. Leningr. State Univ 2 (1988), 31–34.
V. V. Makeev, Equipartition of a continuous mass distribution, Journal of Mathematical Sciences 140 (2007), no. 4, 551–557.
Samuel J. Maltby, Trisecting a rectangle, J. Combin. Theory Ser. A 66 (1994), no. 1, 40–52. MR 1273290, DOI 10.1016/0097-3165(94)90049-3
Jiří Matoušek, Construction of $\epsilon$-nets, Discrete Comput. Geom. 5 (1990), no. 5, 427–448. ACM Symposium on Computational Geometry (Saarbrücken, 1989). MR 1064574, DOI 10.1007/BF02187804
Jiří Matoušek, Efficient partition trees, Discrete Comput. Geom. 8 (1992), no. 3, 315–334. ACM Symposium on Computational Geometry (North Conway, NH, 1991). MR 1174360, DOI 10.1007/BF02293051
Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299, DOI 10.1007/978-1-4613-0039-7
J. Matoušek, Using the Borsuk-Ulam theorem: lectures on topological methods in combinatorics and geometry, Springer, 2003.
R. Daniel Mauldin (ed.), The Scottish Book, Birkhäuser, Boston, MA, 1981. Mathematics from the Scottish Café; Including selected papers presented at the Scottish Book Conference held at North Texas State University, Denton, Tex., May 1979. MR 666400
D. G. Mead, Dissection of the hypercube into simplexes, Proc. Amer. Math. Soc. 76 (1979), no. 2, 302–304. MR 537093, DOI 10.1090/S0002-9939-1979-0537093-6
Nimrod Megiddo, Partitioning with two lines in the plane, J. Algorithms 6 (1985), no. 3, 430–433. MR 800732, DOI 10.1016/0196-6774(85)90011-2
Frédéric Meunier, Discrete splittings of the necklace, Math. Oper. Res. 33 (2008), no. 3, 678–688. MR 2442647, DOI 10.1287/moor.1080.0311
Frédéric Meunier, Simplotopal maps and necklace splitting, Discrete Math. 323 (2014), 14–26. MR 3166050, DOI 10.1016/j.disc.2014.01.008
Peter Mani-Levitska, Siniša Vrećica, and Rade Živaljević, Topology and combinatorics of partitions of masses by hyperplanes, Adv. Math. 207 (2006), no. 1, 266–296. MR 2264074, DOI 10.1016/j.aim.2005.11.013
Paul Monsky, On dividing a square into triangles, Amer. Math. Monthly 77 (1970), 161–164. MR 252233, DOI 10.2307/2317329
Gabriel Nivasch, An improved, simple construction of many halving edges, Surveys on discrete and computational geometry, Contemp. Math., vol. 453, Amer. Math. Soc., Providence, RI, 2008, pp. 299–305. MR 2405686, DOI 10.1090/conm/453/08804
Kazumiti Numata and Takeshi Tokuyama, Splitting a configuration in a simplex, Algorithmica 9 (1993), no. 6, 649–668. Selections from SIGAL International Symposium on Algorithms (Tokyo, 1990). MR 1221824, DOI 10.1007/BF01190161
Peter Orlik and Hiroaki Terao, Arrangements of hyperplanes, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 300, Springer-Verlag, Berlin, 1992. MR 1217488, DOI 10.1007/978-3-662-02772-1
Dömötör Pálvölgyi, Combinatorial necklace splitting, Electron. J. Combin. 16 (2009), no. 1, Research Paper 79, 8. MR 2529788, DOI 10.37236/168
Christos H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, J. Comput. System Sci. 48 (1994), no. 3, 498–532. 31st Annual Symposium on Foundations of Computer Science (FOCS) (St. Louis, MO, 1990). MR 1279412, DOI 10.1016/S0022-0000(05)80063-7
Ariel D. Procaccia, Cake cutting algorithms, Handbook of computational social choice, Cambridge Univ. Press, New York, 2016, pp. 311–329. MR 3643848
A. Pilz and P. Schnider, Bisecting three classes of lines, arXiv:1909.04419 (2019).
Attila Pór and Pavel Valtr, The partitioned version of the Erdős-Szekeres theorem, Discrete Comput. Geom. 28 (2002), no. 4, 625–637. Discrete and computational geometry and graph drawing (Columbia, SC, 2001). MR 1949905, DOI 10.1007/s00454-002-2894-1
R. Rado, A theorem on general measure, J. London Math. Soc. 21 (1946), 291–300 (1947). MR 21962, DOI 10.1112/jlms/s1-21.4.291
E. A. Ramos, Equipartition of mass distributions by hyperplanes, Discrete Comput. Geom. 15 (1996), no. 2, 147–167. MR 1368272, DOI 10.1007/BF02717729
Edgardo Roldán-Pensado and Pablo Soberón, An extension of a theorem of Yao and Yao, Discrete Comput. Geom. 51 (2014), no. 2, 285–299. MR 3164167, DOI 10.1007/s00454-014-9568-7
Sambuddha Roy and William Steiger, Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem, Graphs Combin. 23 (2007), no. suppl. 1, 331–341. MR 2320639, DOI 10.1007/s00373-007-0716-1
D. Rudenko, On equidissection of balanced polygons, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 403 (2012), no. Teoriya Predstavleniĭ, Dinamicheskie Sistemy, Kombinatornye Metody. XXI, 142–157, 200 (English, with English and Russian summaries); English transl., J. Math. Sci. (N.Y.) 190 (2013), no. 3, 486–495. MR 3029586, DOI 10.1007/s10958-013-1265-1
Toshinori Sakai, Balanced convex partitions of measures in $\Bbb R^2$, Graphs Combin. 18 (2002), no. 1, 169–192. MR 1892442, DOI 10.1007/s003730200011
Leonard J. Schulman, An equipartition of planar sets, Discrete Comput. Geom. 9 (1993), no. 3, 257–266. MR 1204783, DOI 10.1007/BF02189322
P. Schnider, Equipartitions with wedges and cones, arXiv:1910.13352 (2019).
Patrick Schnider, Ham-sandwich cuts and center transversals in subspaces, Discrete Comput. Geom. 64 (2020), no. 4, 1192–1209. MR 4183361, DOI 10.1007/s00454-020-00196-x
Paul R. Scott, Equipartition of convex bodies, Bull. Austral. Math. Soc. 42 (1990), no. 1, 141–144. MR 1066369, DOI 10.1017/S0004972700028240
Micha Sharir, An improved bound for $k$-sets in four dimensions, Combin. Probab. Comput. 20 (2011), no. 1, 119–129. MR 2745681, DOI 10.1017/S0963548310000143
T. C. Shermer, A linear algorithm for bisecting a polygon, Information Processing Letters 41 (1992), no. 3, 135–140.
Gábor Simonyi, Necklace bisection with one cut less than needed, Electron. J. Combin. 15 (2008), no. 1, Note 16, 5. MR 2411462, DOI 10.37236/891
Steven Simon, Measure equipartitions via finite Fourier analysis, Geom. Dedicata 179 (2015), 217–228. MR 3424667, DOI 10.1007/s10711-015-0077-5
Steven Simon, Hyperplane equipartitions plus constraints, J. Combin. Theory Ser. A 161 (2019), 29–50. MR 3861769, DOI 10.1016/j.jcta.2018.07.012
Pablo Soberón, Balanced convex partitions of measures in $\Bbb R^d$, Mathematika 58 (2012), no. 1, 71–76. MR 2891160, DOI 10.1112/S0025579311001914
Pablo Soberón, Gerrymandering, sandwiches, and topology, Notices Amer. Math. Soc. 64 (2017), no. 9, 1010–1013. MR 3699775, DOI 10.1090/noti1582
E. Sperner, Neuer beweis für die invarianz der dimensionszahl und des gebietes, Abh. Math. Sem. Univ. Hamburg 6 (1928), no. 1, 265–272 (German). MR 3069504, DOI 10.1007/BF02940617
M. Sharir, S. Smorodinsky, and G. Tardos, An improved bound for $k$-sets in three dimensions, Discrete Comput. Geom. 26 (2001), no. 2, 195–204. ACM Symposium on Computational Geometry (Hong Kong, 2000). MR 1843436, DOI 10.1145/336154.336173
A. H. Stone and J. W. Tukey, Generalized “sandwich” theorems, Duke Math. J. 9 (1942), 356–359. MR 7036, DOI 10.1215/S0012-7094-42-00925-6
József Solymosi and Terence Tao, An incidence theorem in higher dimensions, Discrete Comput. Geom. 48 (2012), no. 2, 255–280. MR 2946447, DOI 10.1007/s00454-012-9420-x
H. Steinhaus, A note on the ham sandwich theorem, Mathesis Polska 9 (1938), 26–28.
Hugo Steinhaus, Sur la division des ensembles de l’espace par les plans et des ensembles plans par les cercles, Fund. Math. 33 (1945), 245–263 (French). MR 17514, DOI 10.4064/fm-33-1-245-263
H. Steinlein, Borsuk’s antipodal theorem and its generalizations and applications: a survey, Topological methods in nonlinear analysis, Sém. Math. Sup., vol. 95, Presses Univ. Montréal, Montreal, QC, 1985, pp. 166–235. MR 801938
Ivan Stojmenović, Bisections and ham-sandwich cuts of convex polygons and polyhedra, Inform. Process. Lett. 38 (1991), no. 1, 15–21. MR 1103695, DOI 10.1016/0020-0190(91)90209-Z
Francis Edward Su, Rental harmony: Sperner’s lemma in fair division, Amer. Math. Monthly 106 (1999), no. 10, 930–942. MR 1732499, DOI 10.2307/2589747
Walter Stromquist and D. R. Woodall, Sets on which several measures agree, J. Math. Anal. Appl. 108 (1985), no. 1, 241–248. MR 791146, DOI 10.1016/0022-247X(85)90021-6
William Steiger and Jihui Zhao, Generalized ham-sandwich cuts, Discrete Comput. Geom. 44 (2010), no. 3, 535–545. MR 2679052, DOI 10.1007/s00454-009-9225-8
John Thomas, A dissection problem, Math. Mag. 41 (1968), 187–191. MR 236805, DOI 10.2307/2689143
G. Tóth, Point sets with many $k$-sets, Discrete Comput. Geom. 26 (2001), no. 2, 187–194. ACM Symposium on Computational Geometry (Hong Kong, 2000). MR 1843435, DOI 10.1007/s004540010022
Helge Tverberg and Siniša Vrećica, On generalizations of Radon’s theorem and the ham sandwich theorem, European J. Combin. 14 (1993), no. 3, 259–264. MR 1215336, DOI 10.1006/eujc.1993.1029
M. Uno, T. Kawano, and M. Kano, Bisections of two sets of points in the plane lattice, IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences E92-A (2009), no. 2, 502–507.
Siniša T. Vrećica and Rade T. Živaljević, The ham sandwich theorem revisited, Israel J. Math. 78 (1992), no. 1, 21–32. MR 1194956, DOI 10.1007/BF02801568
S. T. Vrećica and R. T. Živaljević, Conical equipartitions of mass distributions, Discrete Comput. Geom. 25 (2001), no. 3, 335–350. MR 1815436, DOI 10.1007/s00454-001-0002-6
Siniša T. Vrećica and Rade T. Živaljević, Arrangements, equivariant maps and partitions of measures by $k$-fans, Discrete and computational geometry, Algorithms Combin., vol. 25, Springer, Berlin, 2003, pp. 829–848. MR 2038911, DOI 10.1007/978-3-642-55566-4_{4}0
S. T. Vrećica and R. T. Živaljević, Hyperplane mass equipartition problem and the shielding functions of Ramos, arXiv:1508.01552 (2015).
Uli Wagner, $k$-sets and $k$-facets, Surveys on discrete and computational geometry, Contemp. Math., vol. 453, Amer. Math. Soc., Providence, RI, 2008, pp. 443–513. MR 2405692, DOI 10.1090/conm/453/08810
Dietrich Weller, Fair division of a measurable space, J. Math. Econom. 14 (1985), no. 1, 5–17. MR 816212, DOI 10.1016/0304-4068(85)90023-0
Dan E. Willard, Polygon retrieval, SIAM J. Comput. 11 (1982), no. 1, 149–165. MR 646770, DOI 10.1137/0211012
A. Xue and P. Soberón, Balanced convex partitions of lines in the plane, arXiv:1910.06231 (2019); to appear in Discrete & Computational Geometry.
F. Frances Yao, David P. Dobkin, Herbert Edelsbrunner, and Michael S. Paterson, Partitioning space for range queries, SIAM J. Comput. 18 (1989), no. 2, 371–384. MR 986673, DOI 10.1137/0218025
A. C. Yao and F. F. Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing (1985), 163–168.
Liping Yuan, Carol T. Zamfirescu, and Tudor I. Zamfirescu, Dissecting the square into five congruent parts, Discrete Math. 339 (2016), no. 1, 288–298. MR 3404490, DOI 10.1016/j.disc.2015.08.009
Joshua Zahl, A Szemerédi-Trotter type theorem in $\Bbb {R}^4$, Discrete Comput. Geom. 54 (2015), no. 3, 513–572. MR 3392965, DOI 10.1007/s00454-015-9717-7
Thomas Zaslavsky, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, Mem. Amer. Math. Soc. 1 (1975), no. issue 1, 154, vii+102. MR 357135, DOI 10.1090/memo/0154
Rade T. Živaljević, Illumination complexes, $\Delta$-zonotopes, and the polyhedral curtain theorem, Comput. Geom. 48 (2015), no. 3, 225–236. MR 3276401, DOI 10.1016/j.comgeo.2014.10.003
Rade T. Živaljević, Topological methods, Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., CRC, Boca Raton, FL, 1997, pp. 209–224. MR 1730167
Rade T. Živaljević and Siniša T. Vrećica, An extension of the ham sandwich theorem, Bull. London Math. Soc. 22 (1990), no. 2, 183–186. MR 1045292, DOI 10.1112/blms/22.2.183
Rade T. Živaljević and Siniša T. Vrećica, The colored Tverberg’s problem and complexes of injective functions, J. Combin. Theory Ser. A 61 (1992), no. 2, 309–318. MR 1185000, DOI 10.1016/0097-3165(92)90028-S

AMS Website Down

Bulletin of the American Mathematical Society

A survey of mass partitions
HTML articles powered by AMS MathViewer

Abstract: