A survey of mass partitions. (English) Zbl 1505.55005
Summary: 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.
MSC:
| 55M20 | Fixed points and coincidences in algebraic topology |
| 28A75 | Length, area, volume, other geometric measure theory |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 52C35 | Arrangements of points, flats, hyperplanes (aspects of discrete geometry) |
| 52-02 | Research exposition (monographs, survey articles) pertaining to convex and discrete geometry |
| 55-02 | Research exposition (monographs, survey articles) pertaining to algebraic topology |
Keywords:
mass partition problems; survey; ham sandwich theorem; hyperplanes; convex partitions; discrete; continuous; Borsuk-UlamReferences:
| [1] | Akiyama, J.; Alon, N., Disjoint simplices and geometric hypergraphs. Combinatorial Mathematics: Proceedings of the Third International Conference, New York, 1985, Ann. New York Acad. Sci. 555, 1-3 (1989), New York Acad. Sci., New York · Zbl 0734.05064 · doi:10.1111/j.1749-6632.1989.tb22429.x |
| [2] | Aichholzer, Oswin; Atienza, Nieves; D\'{\i }az-B\'{a}\~{n}ez, Jos\'{e} M.; Fabila-Monroy, Ruy; Flores-Pe\~{n}aloza, David; P\'{e}rez-Lantero, Pablo; Vogtenhuber, Birgit; Urrutia, Jorge, Computing balanced islands in two colored point sets in the plane, Inform. Process. Lett., 135, 28-32 (2018) · Zbl 1476.68264 · doi:10.1016/j.ipl.2018.02.008 |
| [3] | A. Akopyan, S. Avvakumov, and R. N. Karasev, Convex fair partitions into an arbitrary number of pieces, 1804.03057 (2018). |
| [4] | Abbott, Timothy G.; Burr, Michael A.; Chan, Timothy M.; Demaine, Erik D.; Demaine, Martin L.; Hugg, John; Kane, Daniel; Langerman, Stefan; Nelson, Jelani; Rafalin, Eynat; Seyboth, Kathryn; Yeung, Vincent, Dynamic ham-sandwich cuts in the plane, Comput. Geom., 42, 5, 419-428 (2009) · Zbl 1181.65029 · doi:10.1016/j.comgeo.2008.09.008 |
| [5] | Alon, Noga; B\'{a}r\'{a}ny, Imre; F\"{u}redi, Zolt\'{a}n; Kleitman, Daniel J., Point selections and weak \(\epsilon \)-nets for convex hulls, Combin. Probab. Comput., 1, 3, 189-200 (1992) · Zbl 0797.52004 · doi:10.1017/S0963548300000225 |
| [6] | Aronov, Boris; Chazelle, Bernard; Edelsbrunner, Herbert; Guibas, Leonidas J.; Sharir, Micha; Wenger, Rephael, Points and triangles in the plane and halving planes in space, Discrete Comput. Geom., 6, 5, 435-442 (1991) · Zbl 0764.68057 · doi:10.1007/BF02574700 |
| [7] | Armaselu, Bogdan; Daescu, Ovidiu, Algorithms for fair partitioning of convex polygons, Theoret. Comput. Sci., 607, part 3, 351-362 (2015) · Zbl 1332.68263 · doi:10.1016/j.tcs.2015.08.003 |
| [8] | Agarwal, Pankaj K.; Erickson, Jeff, Geometric range searching and its relatives. Advances in discrete and computational geometry, South Hadley, MA, 1996, Contemp. Math. 223, 1-56 (1999), Amer. Math. Soc., Providence, RI · Zbl 0916.68031 · doi:10.1090/conm/223/03131 |
| [9] | \'{A}brego, Bernardo M.; Fern\'{a}ndez-Merchant, Silvia; Salazar, Gelasio, The rectilinear crossing number of \(K_n\): closing in (or are we?). Thirty essays on geometric graph theory, 5-18 (2013), Springer, New York · Zbl 1272.05029 · doi:10.1007/978-1-4614-0110-0\_2 |
| [10] | Asada, Megumi; Frick, Florian; Pisharody, Vivek; Polevy, Maxwell; Stoner, David; Tsang, Ling Hei; Wellner, Zoe, Fair division and generalizations of Sperner- and KKM-type results, SIAM J. Discrete Math., 32, 1, 591-610 (2018) · Zbl 1385.54013 · doi:10.1137/17M1116210 |
| [11] | N. Alon and A. Graur, Efficient splitting of measures and necklaces, arXiv:2006.16613 (2020). |
| [12] | Alon, Noga; Grytczuk, Jaros\l aw; Laso\'{n}, Micha\l; Micha\l ek, Mateusz, Splitting necklaces and measurable colorings of the real line, Proc. Amer. Math. Soc., 137, 5, 1593-1599 (2009) · Zbl 1229.05258 · doi:10.1090/S0002-9939-08-09699-8 |
| [13] | Aurenhammer, F.; Hoffmann, F.; Aronov, B., Minkowski-type theorems and least-squares clustering, Algorithmica, 20, 1, 61-76 (1998) · Zbl 0895.68135 · doi:10.1007/PL00009187 |
| [14] | Arocha, J.; Jer\'{o}nimo-Castro, J.; Montejano, L.; Rold\'{a}n-Pensado, E., On a conjecture of Gr\"{u}nbaum concerning partitions of convex sets, Period. Math. Hungar., 60, 1, 41-47 (2010) · Zbl 1224.52003 · doi:10.1007/s10998-010-1041-7 |
| [15] | Akopyan, Arseniy; Karasev, Roman, Cutting the same fraction of several measures, Discrete Comput. Geom., 49, 2, 402-410 (2013) · Zbl 1279.52005 · doi:10.1007/s00454-012-9450-4 |
| [16] | S. Avvakumov and R. Karasev, Equipartition of a segment, 2009.09862 (2020). |
| [17] | Akiyama, J.; Kaneko, A.; Kano, M.; Nakamura, G.; Rivera-Campo, E.; Tokunaga, S.; Urrutia, J., Radial perfect partitions of convex sets in the plane. Discrete and computational geometry, Tokyo, 1998, Lecture Notes in Comput. Sci. 1763, 1-13 (2000), Springer, Berlin · Zbl 0981.52004 · doi:10.1007/978-3-540-46515-7\_1 |
| [18] | Alon, Noga, Splitting necklaces, Adv. in Math., 63, 3, 247-253 (1987) · Zbl 0635.05008 · doi:10.1016/0001-8708(87)90055-7 |
| [19] | 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. |
| [20] | Avis, David, Nonpartitionable point sets, Inform. Process. Lett., 19, 3, 125-129 (1984) · Zbl 0564.51007 · doi:10.1016/0020-0190(84)90090-5 |
| [21] | Alon, Noga; West, Douglas B., The Borsuk-Ulam theorem and bisection of necklaces, Proc. Amer. Math. Soc., 98, 4, 623-628 (1986) · Zbl 0614.05005 · doi:10.2307/2045739 |
| [22] | Barbanel, Julius B., The geometry of efficient fair division, x+461 pp. (2005), Cambridge University Press, Cambridge · Zbl 1071.91001 · doi:10.1017/CBO9780511546679 |
| [23] | Buck, R. C.; Buck, Ellen F., Equipartition of convex sets, Math. Mag., 22, 195-198 (1949) · doi:10.2307/3029182 |
| [24] | B\'{a}r\'{a}ny, Imre; Blagojevi\'{c}, Pavle; Dimitrijevi\'{c} Blagojevi\'{c}, Aleksandra, Functions, measures, and equipartitioning convex \(k\)-fans, Discrete Comput. Geom., 49, 2, 382-401 (2013) · Zbl 1263.60007 · doi:10.1007/s00454-012-9467-8 |
| [25] | Bereg, Sergey; Bose, Prosenjit; Kirkpatrick, David, Equitable subdivisions within polygonal regions, Comput. Geom., 34, 1, 20-27 (2006) · Zbl 1098.65023 · doi:10.1016/j.comgeo.2005.06.003 |
| [26] | P. V. M. Blagojevi\'c, A. D. Blagojevi\'c, and R. N. Karasev, More bisections by hyperplane arrangements, 1809.05364 (2018). · Zbl 1490.52015 |
| [27] | B\'{a}r\'{a}ny, Imre; Blagojevi\'{c}, Pavle; Sz\H{u}cs, Andr\'{a}s, Equipartitioning by a convex 3-fan, Adv. Math., 223, 2, 579-593 (2010) · Zbl 1190.52001 · doi:10.1016/j.aim.2009.08.016 |
| [28] | 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. · Zbl 0971.68625 |
| [29] | 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. |
| [30] | Blagojevi\'{c}, Pavle V. M.; Dimitrijevi\'{c} Blagojevi\'{c}, Aleksandra S., Using equivariant obstruction theory in combinatorial geometry, Topology Appl., 154, 14, 2635-2655 (2007) · Zbl 1158.55009 · doi:10.1016/j.topol.2007.04.007 |
| [31] | Blagojevi\'{c}, Pavle V. M.; Dimitrijevi\'{c} Blagojevi\'{c}, Aleksandra, A problem related to B\'{a}r\'{a}ny-Gr\"{u}nbaum conjecture, Filomat, 27, 1, 109-113 (2013) · Zbl 1340.52014 · doi:10.2298/FIL1301109B |
| [32] | Bose, Prosenjit; Demaine, Erik D.; Hurtado, Ferran; Iacono, John; Langerman, Stefan; Morin, Pat, Geodesic ham-sandwich cuts, Discrete Comput. Geom., 37, 3, 325-339 (2007) · Zbl 1136.90390 · doi:10.1007/s00454-006-1287-2 |
| [33] | Bereg, Sergey, Equipartitions of measures by 2-fans, Discrete Comput. Geom., 34, 1, 87-96 (2005) · Zbl 1073.52003 · doi:10.1007/s00454-004-1151-1 |
| [34] | Bereg, Sergey, Computing generalized ham-sandwich cuts, Inform. Process. Lett., 112, 13, 532-534 (2012) · Zbl 1243.68306 · doi:10.1016/j.ipl.2012.03.013 |
| [35] | Bespamyatnikh, Sergei, On partitioning a cake. Discrete and computational geometry, Lecture Notes in Comput. Sci. 2866, 60-71 (2003), Springer, Berlin · Zbl 1179.52002 · doi:10.1007/978-3-540-44400-8\_7 |
| [36] | Blagojevi\'{c}, Pavle V. M.; Frick, Florian; Haase, Albert; Ziegler, G\"{u}nter M., Hyperplane mass partitions via relative equivariant obstruction theory, Doc. Math., 21, 735-771 (2016) · Zbl 1361.55007 |
| [37] | Blagojevi\'{c}, Pavle V. M.; Frick, Florian; Haase, Albert; Ziegler, G\"{u}nter M., Topology of the Gr\"{u}nbaum-Hadwiger-Ramos hyperplane mass partition problem, Trans. Amer. Math. Soc., 370, 10, 6795-6824 (2018) · Zbl 1396.52011 · doi:10.1090/tran/7528 |
| [38] | B\'{a}r\'{a}ny, I.; F\"{u}redi, Z.; Lov\'{a}sz, L., On the number of halving planes, Combinatorica, 10, 2, 175-183 (1990) · Zbl 0718.52009 · doi:10.1007/BF02123008 |
| [39] | Balitskiy, Alexey; Garber, Alexey; Karasev, Roman, Another ham sandwich in the plane, Ann. Comb., 19, 2, 235-242 (2015) · Zbl 1321.52022 · doi:10.1007/s00026-015-0270-0 |
| [40] | Bose, Prosenjit; Guibas, Leonidas; Lubiw, Anna; Overmars, Mark; Souvaine, Diane; Urrutia, Jorge, The floodlight problem, Internat. J. Comput. Geom. Appl., 7, 1-2, 153-163 (1997) · Zbl 0877.68114 · doi:10.1142/S0218195997000090 |
| [41] | B\'{a}r\'{a}ny, Imre; Hubard, Alfredo; Jer\'{o}nimo, Jes\'{u}s, Slicing convex sets and measures by a hyperplane, Discrete Comput. Geom., 39, 1-3, 67-75 (2008) · Zbl 1142.52004 · doi:10.1007/s00454-007-9021-2 |
| [42] | Bereg, Sergey; Hurtado, Ferran; Kano, Mikio; Korman, Matias; Lara, Dolores; Seara, Carlos; Silveira, Rodrigo I.; Urrutia, Jorge; Verbeek, Kevin, Balanced partitions of 3-colored geometric sets in the plane, Discrete Appl. Math., 181, 21-32 (2015) · Zbl 1304.05008 · doi:10.1016/j.dam.2014.10.015 |
| [43] | Bespamyatnikh, S.; Kirkpatrick, D.; Snoeyink, J., Generalizing ham sandwich cuts to equitable subdivisions, Discrete Comput. Geom., 24, 4, 605-622 (2000) · Zbl 0966.68156 · doi:10.1145/304893.304909 |
| [44] | Bose, Prosenjit; Langerman, Stefan, Weighted ham-sandwich cuts. Discrete and computational geometry, Lecture Notes in Comput. Sci. 3742, 48-53 (2005), Springer, Berlin · Zbl 1136.52306 · doi:10.1007/11589440\_5 |
| [45] | B\'{a}r\'{a}ny, I.; Matou\v{s}ek, J., Simultaneous partitions of measures by \(k\)-fans, Discrete Comput. Geom., 25, 3, 317-334 (2001) · Zbl 0989.52009 · doi:10.1007/s00454-001-0003-5 |
| [46] | B\'{a}r\'{a}ny, I.; Matou\v{s}ek, J., Equipartition of two measures by a 4-fan, Discrete Comput. Geom., 27, 3, 293-301 (2002) · Zbl 1002.60006 · doi:10.1007/s00454-001-0071-6 |
| [47] | Bukh, Boris; Matou\v{s}ek, Ji\v{r}\'{\i }; Nivasch, Gabriel, Stabbing simplices by points and flats, Discrete Comput. Geom., 43, 2, 321-338 (2010) · Zbl 1186.52001 · doi:10.1007/s00454-008-9124-4 |
| [48] | Bekker, Boris M.; Netsvetaev, Nikita Yu., Generalized Sperner lemma and subdivisions into simplices of equal volume, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI). J. Math. Sci. (New York), 231 91, 6, 3492-3498 (1998) · Zbl 0907.51007 · doi:10.1007/BF02434927 |
| [49] | Borsuk, K., An application of the theorem on antipodes to the measure theory, Bull. Acad. Polon. Sci. Cl. III., 1, 87-90 (1953) · Zbl 0053.29804 |
| [50] | L. Barba, A. Pilz, and P. Schnider, Sharing a pizza: bisecting masses with two cuts, 1904.02502 (2019). |
| [51] | Blagojevi\'{c}, Pavle V. M.; Pali\'{c}, Nevena; Sober\'{o}n, Pablo; Ziegler, G\"{u}nter M., Cutting a part from many measures, Forum Math. Sigma, 7, Paper No. e37, 34 pp. (2019) · Zbl 1426.52002 · doi:10.1017/fms.2019.33 |
| [52] | Blagojevi\'{c}, Pavle V. M.; Rote, G\"{u}nter; Steinmeyer, Johanna K.; Ziegler, G\"{u}nter M., Convex equipartitions of colored point sets, Discrete Comput. Geom., 61, 2, 355-363 (2019) · Zbl 1407.52031 · doi:10.1007/s00454-017-9959-7 |
| [53] | B\'{a}r\'{a}ny, Imre; Steiger, William, On the expected number of \(k\)-sets, Discrete Comput. Geom., 11, 3, 243-263 (1994) · Zbl 0802.52003 · doi:10.1007/BF02574008 |
| [54] | B\'{a}r\'{a}ny, Imre; Sober\'{o}n, Pablo, Tverberg’s theorem is 50 years old: a survey, Bull. Amer. Math. Soc. (N.S.), 55, 4, 459-492 (2018) · Zbl 1401.52012 · doi:10.1090/bull/1634 |
| [55] | Blagojevi\'{c}, Pavle V. M.; Sober\'{o}n, Pablo, Thieves can make sandwiches, Bull. Lond. Math. Soc., 50, 1, 108-123 (2018) · Zbl 1390.52008 · doi:10.1112/blms.12109 |
| [56] | Brams, Steven J.; Taylor, Alan D., Fair division, xiv+272 pp. (1996), Cambridge University Press, Cambridge · Zbl 0991.91019 · doi:10.1017/CBO9780511598975 |
| [57] | B\'{a}r\'{a}ny, I.; Valtr, P., A positive fraction Erd\H{o}s-Szekeres theorem, Discrete Comput. Geom., 19, 3, Special Issue, 335-342 (1998) · Zbl 0914.52007 · doi:10.1007/PL00009350 |
| [58] | Blagojevi\'{c}, Pavle V. M.; Ziegler, G\"{u}nter M., Convex equipartitions via equivariant obstruction theory, Israel J. Math., 200, 1, 49-77 (2014) · Zbl 1305.52005 · doi:10.1007/s11856-014-1006-6 |
| [59] | Blagojevi\'{c}, Pavle V. M.; Ziegler, G\"{u}nter M., Beyond the Borsuk-Ulam theorem: the topological Tverberg story. A journey through discrete mathematics, 273-341 (2017), Springer, Cham · Zbl 1470.52007 |
| [60] | Beyer, W. A.; Zardecki, Andrew, The early history of the ham sandwich theorem, Amer. Math. Monthly, 111, 1, 58-61 (2004) · Zbl 1047.55500 · doi:10.2307/4145019 |
| [61] | Chan, Yu Hin; Chen, Shujian; Frick, Florian; Hull, J. Tristan, Borsuk-Ulam theorems for products of spheres and Stiefel manifolds revisited, Topol. Methods Nonlinear Anal., 55, 2, 553-564 (2020) · Zbl 1448.55002 · doi:10.12775/tmna.2019.103 |
| [62] | Clarkson, Kenneth L.; Edelsbrunner, Herbert; Guibas, Leonidas J.; Sharir, Micha; Welzl, Emo, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete Comput. Geom., 5, 2, 99-160 (1990) · Zbl 0704.51003 · doi:10.1007/BF02187783 |
| [63] | Chazelle, B.; Friedman, J., A deterministic view of random sampling and its use in geometry, Combinatorica, 10, 3, 229-249 (1990) · Zbl 0715.68036 · doi:10.1007/BF02122778 |
| [64] | Conlon, David; Fox, Jacob; Pach, J\'{a}nos; Sudakov, Benny; Suk, Andrew, Ramsey-type results for semi-algebraic relations, Trans. Amer. Math. Soc., 366, 9, 5043-5065 (2014) · Zbl 1306.14027 · doi:10.1090/S0002-9947-2014-06179-5 |
| [65] | Chazelle, Bernard, Cutting hyperplanes for divide-and-conquer, Discrete Comput. Geom., 9, 2, 145-158 (1993) · Zbl 0784.52018 · doi:10.1007/BF02189314 |
| [66] | Chan, Timothy M., An optimal randomized algorithm for maximum Tukey depth. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 430-436 (2004), ACM, New York · Zbl 1317.68246 |
| [67] | G. W. Cox and R. D. McKelvey, A ham sandwich theorem for general measures, Social Choice and Welfare 1 (1984), no. 1, 75-83. · Zbl 0555.28001 |
| [68] | Courant, Richard; Robbins, Herbert, What Is Mathematics?, xix+521 pp. (1941), Oxford University Press, New York · Zbl 0060.12302 |
| [69] | R. Cole, M. Sharir, and C.-K. Yap, On k-hulls and related problems, Symposium on Theory of Computing, 1984, pp. 154-166. |
| [70] | Dey, T. K., Improved bounds for planar \(k\)-sets and related problems, Discrete Comput. Geom., 19, 3, Special Issue, 373-382 (1998) · Zbl 0899.68107 · doi:10.1007/PL00009354 |
| [71] | Du, Xiumin; Guth, Larry; Li, Xiaochun, A sharp Schr\"{o}dinger maximal estimate in \(\mathbb{R}^2\), Ann. of Math. (2), 186, 2, 607-640 (2017) · Zbl 1378.42011 · doi:10.4007/annals.2017.186.2.5 |
| [72] | Dujmovi\'{c}, Vida; Langerman, Stefan, A center transversal theorem for hyperplanes and applications to graph drawing, Discrete Comput. Geom., 49, 1, 74-88 (2013) · Zbl 1264.52015 · doi:10.1007/s00454-012-9464-y |
| [73] | De Loera, Jes\'{u}s A.; Goaoc, Xavier; Meunier, Fr\'{e}d\'{e}ric; Mustafa, Nabil H., The discrete yet ubiquitous theorems of Carath\'{e}odory, Helly, Sperner, Tucker, and Tverberg, Bull. Amer. Math. Soc. (N.S.), 56, 3, 415-511 (2019) · Zbl 1460.52010 · doi:10.1090/bull/1653 |
| [74] | de Longueville, Mark; Zivaljevi\'{c}, Rade T., Splitting multidimensional necklaces, Adv. Math., 218, 3, 926-939 (2008) · Zbl 1154.05006 · doi:10.1016/j.aim.2008.02.003 |
| [75] | Dold, Albrecht, Simple proofs of some Borsuk-Ulam results. Proceedings of the Northwestern Homotopy Theory Conference, Evanston, Ill., 1982, Contemp. Math. 19, 65-69 (1983), Amer. Math. Soc., Providence, RI · Zbl 0521.55002 · doi:10.1090/conm/019/711043 |
| [76] | Dol\cprime nikov, V. L., A generalization of the sandwich theorem, Mat. Zametki. Math. Notes, 52 52, 1-2, 771-779 (1993) (1992) · Zbl 0787.52003 · doi:10.1007/BF01236771 |
| [77] | Edelsbrunner, Herbert, Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science 10, xvi+423 pp. (1987), Springer-Verlag, Berlin · Zbl 0634.52001 · doi:10.1007/978-3-642-61568-9 |
| [78] | Erd\H{o}s, P.; Lov\'{a}sz, L.; Simmons, A.; Straus, E. G., Dissection graphs of planar point sets. A survey of combinatorial theory, Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971, 139-149 (1973), North-Holland, Amsterdam · Zbl 0258.05112 |
| [79] | Edelsbrunner, H.; Valtr, P.; Welzl, E., Cutting dense point sets in half, Discrete Comput. Geom., 17, 3, 243-255 (1997) · Zbl 0870.68153 · doi:10.1007/PL00009291 |
| [80] | Fadell, Edward; Husseini, Sufian, An ideal-valued cohomological index theory with applications to Borsuk-Ulam and Bourgin-Yang theorems, Ergodic Theory Dynam. Systems, \(8^*\), Charles Conley Memorial Issue, 73-85 (1988) · Zbl 0657.55002 · doi:10.1017/S0143385700009342 |
| [81] | M. Fradelizi, A. Hubard, M. Meyer, E. Rold\'an-Pensado, and A. Zvavitch, Equipartitions and Mahler volumes of symmetric convex bodies, 1904.10765 (2019). |
| [82] | Fruchard, Augustin; Magazinov, Alexander, Fair partitioning by straight lines. Convexity and discrete geometry including graph theory, Springer Proc. Math. Stat. 148, 161-165 (2016), Springer, [Cham] · Zbl 1373.52003 · doi:10.1007/978-3-319-28186-5\_14 |
| [83] | Fox, Jacob; Pach, J\'{a}nos; Suk, Andrew, A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing, SIAM J. Comput., 45, 6, 2199-2223 (2016) · Zbl 1353.05090 · doi:10.1137/15M1007355 |
| [84] | A. Filos-Ratsikas, A. Hollender, K. Sotiraki, and M. Zampetakis, A topological characterization of modulo-p arguments and implications for necklace splitting, 2003.11974 (2020). |
| [85] | Goldberg, Paul W.; Filos-Ratsikas, Aris, The complexity of splitting necklaces and bisecting ham sandwiches. STOC’19-Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 638-649 (2019), ACM, New York · Zbl 1433.68157 · doi:10.1145/3313276.3316334 |
| [86] | Guth, Larry; Hickman, Jonathan; Iliopoulou, Marina, Sharp estimates for oscillatory integral operators via polynomial partitioning, Acta Math., 223, 2, 251-376 (2019) · Zbl 1430.42016 · doi:10.4310/acta.2019.v223.n2.a2 |
| [87] | Guth, Larry; Katz, Nets Hawk, On the Erd\H{o}s distinct distances problem in the plane, Ann. of Math. (2), 181, 1, 155-190 (2015) · Zbl 1310.52019 · doi:10.4007/annals.2015.181.1.2 |
| [88] | M. G\"o\"os, P. Kamath, K, Sotiraki, and M. Zampetakis, On the complexity of modulo-q arguments and the Chevalley-warning theorem, arXiv:1912.04467 (2019). |
| [89] | Gromov, M., Isoperimetry of waists and concentration of maps, Geom. Funct. Anal., 13, 1, 178-215 (2003) · Zbl 1044.46057 · doi:10.1007/s000390300004 |
| [90] | Gr\"{u}nbaum, B., Partitions of mass-distributions and of convex bodies by hyperplanes, Pacific J. Math., 10, 1257-1261 (1960) · Zbl 0101.14603 |
| [91] | Guth, Larry, A restriction estimate using polynomial partitioning, J. Amer. Math. Soc., 29, 2, 371-413 (2016) · Zbl 1342.42010 · doi:10.1090/jams827 |
| [92] | Guth, Larry, Polynomial methods in combinatorics, University Lecture Series 64, ix+273 pp. (2016), American Mathematical Society, Providence, RI · Zbl 1388.05003 · doi:10.1090/ulect/064 |
| [93] | Goldberg, Charles H.; West, Douglas B., Bisection of circle colorings, SIAM J. Algebraic Discrete Methods, 6, 1, 93-106 (1985) · Zbl 0558.05008 · doi:10.1137/0606010 |
| [94] | Hadwiger, H., Simultane Vierteilung zweier K\"{o}rper, Arch. Math. (Basel), 17, 274-278 (1966) · Zbl 0137.41501 · doi:10.1007/BF01899586 |
| [95] | Hubard, Alfredo; Karasev, Roman, Bisecting measures with hyperplane arrangements, Math. Proc. Cambridge Philos. Soc., 169, 3, 639-647 (2020) · Zbl 1498.52038 · doi:10.1017/s0305004119000380 |
| [96] | Holmsen, Andreas F.; Kyn\v{c}l, Jan; Valculescu, Claudiu, Near equipartitions of colored point sets, Comput. Geom., 65, 35-42 (2017) · Zbl 1377.65026 · doi:10.1016/j.comgeo.2017.05.001 |
| [97] | A. Hollender, The classes PPA-k: Existence from arguments modulo k, International Conference on Web and Internet Economics, Springer, 2019, pp. 214-227. · Zbl 1435.68107 |
| [98] | Hobby, Charles R.; Rice, John R., A moment problem in \(L_1\) approximation, Proc. Amer. Math. Soc., 16, 665-670 (1965) · Zbl 0142.09802 · doi:10.2307/2033900 |
| [99] | M. Humphreys, Can compactness constrain the Gerrymander?, Irish Political Studies 26 (2011), no. 4, 513-520. |
| [100] | Haussler, David; Welzl, Emo, \( \epsilon \)-nets and simplex range queries, Discrete Comput. Geom., 2, 2, 127-151 (1987) · Zbl 0619.68056 · doi:10.1007/BF02187876 |
| [101] | Iriyeh, Hiroshi; Shibata, Masataka, Symmetric Mahler’s conjecture for the volume product in the \(3\)-dimensional case, Duke Math. J., 169, 6, 1077-1134 (2020) · Zbl 1439.52007 · doi:10.1215/00127094-2019-0072 |
| [102] | Ito, Hiro; Uehara, Hideyuki; Yokoyama, Mitsuo, 2-dimension ham sandwich theorem for partitioning into three convex pieces. Discrete and computational geometry, Tokyo, 1998, Lecture Notes in Comput. Sci. 1763, 129-157 (2000), Springer, Berlin · Zbl 0973.52005 · doi:10.1007/978-3-540-46515-7\_11 |
| [103] | D. Joji\'c, G. Panina, and R. T. Zivaljevi\'c, Splitting necklaces, with constraints, Oberwolfach Preprints OWP-2020-03 (2020). · Zbl 1467.05281 |
| [104] | Karas\"{e}v, R. N., Topological methods in combinatorial geometry, Uspekhi Mat. Nauk. Russian Math. Surveys, 63 63, 6, 1031-1078 (2008) · Zbl 1200.52001 · doi:10.1070/RM2008v063n06ABEH004578 |
| [105] | Karasev, R. N., Equipartition of a measure by \((Z_p)^k\)-invariant fans, Discrete Comput. Geom., 43, 2, 477-481 (2010) · Zbl 1208.52020 · doi:10.1007/s00454-009-9138-6 |
| [106] | Karasev, R. N., Knaster’s problem for \((Z_2)^k\)-symmetric subsets of the sphere \(S^{2^k-1}\), Discrete Comput. Geom., 44, 2, 429-438 (2010) · Zbl 1200.55006 · doi:10.1007/s00454-009-9215-x |
| [107] | Kasimatis, E. A., Dissections of regular polygons into triangles of equal areas, Discrete Comput. Geom., 4, 4, 375-381 (1989) · Zbl 0675.52005 · doi:10.1007/BF02187738 |
| [108] | 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. · Zbl 1436.55003 |
| [109] | Karasev, Roman; Hubard, Alfredo; Aronov, Boris, Convex equipartitions: the spicy chicken theorem, Geom. Dedicata, 170, 263-279 (2014) · Zbl 1301.52010 · doi:10.1007/s10711-013-9879-5 |
| [110] | Kaneko, Atsushi; Kano, M., Discrete geometry on red and blue points in the plane-a survey. Discrete and computational geometry, Algorithms Combin. 25, 551-570 (2003), Springer, Berlin · Zbl 1079.52505 · doi:10.1007/978-3-642-55566-4\_25 |
| [111] | Kano, Mikio; Kyn\v{c}l, Jan, The hamburger theorem, Comput. Geom., 68, 167-173 (2018) · Zbl 1380.05068 · doi:10.1016/j.comgeo.2017.06.012 |
| [112] | B. Knaster, C. Kuratowski, and S. Mazurkiewicz, Ein Beweis des Fixpunktsatzes f\"ur n-dimensionale Simplexe, Fundamenta Mathematicae 14 (1929), no. 1, 132-137. · JFM 55.0972.01 |
| [113] | B. Knudsen, Configuration spaces in algebraic topology, 1803.11165 (2018). |
| [114] | Karasev, Roman N.; Rold\'{a}n-Pensado, Edgardo; Sober\'{o}n, Pablo, Measure partitions using hyperplanes with fixed directions, Israel J. Math., 212, 2, 705-728 (2016) · Zbl 1344.52006 · doi:10.1007/s11856-016-1303-z |
| [115] | Kuratowski, K.; Steinhaus, H., Une application g\'{e}om\'{e}trique du th\'{e}or\`eme de Brouwer sur les points invariants, Bull. Acad. Polon. Sci. Cl. III., 1, 83-86 (1953) · Zbl 0053.12103 |
| [116] | J. M. Keil and J.-R. Sack, Minimum decompositions of polygonal objects, Computational Geometry, Elsevier, 1985, pp. 197-216. |
| [117] | G. O. H. Katona, A. Schrijver, T. Szonyi, and G. S\'agi (eds.), Open problems, pp. 355-365, Springer Berlin Heidelberg, Berlin, Heidelberg, 2010. · Zbl 1205.05003 |
| [118] | Kov\'{a}cs, Istv\'{a}n; T\'{o}th, G\'{e}za, Dense point sets with many halving lines, Discrete Comput. Geom., 64, 3, 965-984 (2020) · Zbl 1462.52027 · doi:10.1007/s00454-019-00080-3 |
| [119] | M. Kano and J. Urrutia, Discrete geometry on red and blue points in the plane-a survey, Graphs and Combinatorics (2020), 1-53. · Zbl 1459.05032 |
| [120] | Laso\'{n}, Micha\l, Obstacles for splitting multidimensional necklaces, Proc. Amer. Math. Soc., 143, 11, 4655-4668 (2015) · Zbl 1320.05136 · doi:10.1090/S0002-9939-2015-12611-1 |
| [121] | Lehec, Joseph, On the Yao-Yao partition theorem, Arch. Math. (Basel), 92, 4, 366-376 (2009) · Zbl 1185.68784 · doi:10.1007/s00013-009-3013-9 |
| [122] | Levi, Friedrich, Die Drittelungskurve, Math. Z., 31, 1, 339-345 (1930) · JFM 55.0434.02 · doi:10.1007/BF01246415 |
| [123] | Lo, Chi-Yuan; Matou\v{s}ek, J.; Steiger, W., Algorithms for ham-sandwich cuts, Discrete Comput. Geom., 11, 4, 433-452 (1994) · Zbl 0806.68061 · doi:10.1007/BF02574017 |
| [124] | S. Langerman and W. Steiger, Optimization in arrangements, STACS 2003, Springer, Berlin, Heidelberg, Berlin, Heidelberg, February 2003, pp. 50-61. · Zbl 1036.90512 |
| [125] | E. Le\'on and G. M. Ziegler, Spaces of convex n-partitions, New Trends in Intuitive Geometry, Springer Berlin Heidelberg, Berlin, Heidelberg, 2018, pp. 279-306. · Zbl 1444.52008 |
| [126] | V. V. Makeev, Partitioning space in six parts, Vestn. Leningr. State Univ 2 (1988), 31-34. · Zbl 0668.51016 |
| [127] | V. V. Makeev, Equipartition of a continuous mass distribution, Journal of Mathematical Sciences 140 (2007), no. 4, 551-557. · Zbl 1151.52304 |
| [128] | Maltby, Samuel J., Trisecting a rectangle, J. Combin. Theory Ser. A, 66, 1, 40-52 (1994) · Zbl 0797.05030 · doi:10.1016/0097-3165(94)90049-3 |
| [129] | Matou\v{s}ek, Ji\v{r}\'{\i }, Construction of \(\epsilon \)-nets, Discrete Comput. Geom., 5, 5, 427-448 (1990) · Zbl 0701.68040 · doi:10.1007/BF02187804 |
| [130] | Matou\v{s}ek, Ji\v{r}\'{\i }, Efficient partition trees, Discrete Comput. Geom., 8, 3, 315-334 (1992) · Zbl 0752.68088 · doi:10.1007/BF02293051 |
| [131] | Matou\v{s}ek, Ji\v{r}\'{\i }, Lectures on discrete geometry, Graduate Texts in Mathematics 212, xvi+481 pp. (2002), Springer-Verlag, New York · Zbl 0999.52006 · doi:10.1007/978-1-4613-0039-7 |
| [132] | J. Matousek, Using the Borsuk-Ulam theorem: lectures on topological methods in combinatorics and geometry, Springer, 2003. · Zbl 1016.05001 |
| [133] | The Scottish Book, xiii+268 pp. (2 plates) pp. (1981), Birkh\"{a}user, Boston, Mass. · Zbl 0485.01013 |
| [134] | Mead, D. G., Dissection of the hypercube into simplexes, Proc. Amer. Math. Soc., 76, 2, 302-304 (1979) · Zbl 0423.51012 · doi:10.2307/2043008 |
| [135] | Megiddo, Nimrod, Partitioning with two lines in the plane, J. Algorithms, 6, 3, 430-433 (1985) · Zbl 0582.51013 · doi:10.1016/0196-6774(85)90011-2 |
| [136] | Meunier, Fr\'{e}d\'{e}ric, Discrete splittings of the necklace, Math. Oper. Res., 33, 3, 678-688 (2008) · Zbl 1232.05248 · doi:10.1287/moor.1080.0311 |
| [137] | Meunier, Fr\'{e}d\'{e}ric, Simplotopal maps and necklace splitting, Discrete Math., 323, 14-26 (2014) · Zbl 1283.05030 · doi:10.1016/j.disc.2014.01.008 |
| [138] | Mani-Levitska, Peter; Vre\'{c}ica, Sini\v{s}a; Zivaljevi\'{c}, Rade, Topology and combinatorics of partitions of masses by hyperplanes, Adv. Math., 207, 1, 266-296 (2006) · Zbl 1110.68155 · doi:10.1016/j.aim.2005.11.013 |
| [139] | Monsky, Paul, On dividing a square into triangles, Amer. Math. Monthly, 77, 161-164 (1970) · Zbl 0187.19701 · doi:10.2307/2317329 |
| [140] | Nivasch, Gabriel, An improved, simple construction of many halving edges. Surveys on discrete and computational geometry, Contemp. Math. 453, 299-305 (2008), Amer. Math. Soc., Providence, RI · Zbl 1148.68552 · doi:10.1090/conm/453/08804 |
| [141] | Numata, Kazumiti; Tokuyama, Takeshi, Splitting a configuration in a simplex, Algorithmica, 9, 6, 649-668 (1993) · Zbl 0781.68122 · doi:10.1007/BF01190161 |
| [142] | Orlik, Peter; Terao, Hiroaki, Arrangements of hyperplanes, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 300, xviii+325 pp. (1992), Springer-Verlag, Berlin · Zbl 0757.55001 · doi:10.1007/978-3-662-02772-1 |
| [143] | P\'{a}lv\"{o}lgyi, D\"{o}m\"{o}t\"{o}r, Combinatorial necklace splitting, Electron. J. Combin., 16, 1, Research Paper 79, 8 pp. (2009) · Zbl 1186.05017 |
| [144] | Papadimitriou, Christos H., On the complexity of the parity argument and other inefficient proofs of existence, J. Comput. System Sci., 48, 3, 498-532 (1994) · Zbl 0806.68048 · doi:10.1016/S0022-0000(05)80063-7 |
| [145] | Procaccia, Ariel D., Cake cutting algorithms. Handbook of computational social choice, 311-329 (2016), Cambridge Univ. Press, New York · Zbl 1448.91139 |
| [146] | A. Pilz and P. Schnider, Bisecting three classes of lines, 1909.04419 (2019). · Zbl 1525.52013 |
| [147] | P\'{o}r, Attila; Valtr, Pavel, The partitioned version of the Erd\H{o}s-Szekeres theorem, Discrete Comput. Geom., 28, 4, 625-637 (2002) · Zbl 1019.52011 · doi:10.1007/s00454-002-2894-1 |
| [148] | Rado, R., A theorem on general measure, J. London Math. Soc., 21, 291-300 (1947) (1946) · Zbl 0061.09606 · doi:10.1112/jlms/s1-21.4.291 |
| [149] | Ramos, E. A., Equipartition of mass distributions by hyperplanes, Discrete Comput. Geom., 15, 2, 147-167 (1996) · Zbl 0843.68120 · doi:10.1007/BF02717729 |
| [150] | Rold\'{a}n-Pensado, Edgardo; Sober\'{o}n, Pablo, An extension of a theorem of Yao and Yao, Discrete Comput. Geom., 51, 2, 285-299 (2014) · Zbl 1298.52021 · doi:10.1007/s00454-014-9568-7 |
| [151] | Roy, Sambuddha; Steiger, William, Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem, Graphs Combin., 23, suppl. 1, 331-341 (2007) · Zbl 1123.52007 · doi:10.1007/s00373-007-0716-1 |
| [152] | Rudenko, D., On equidissection of balanced polygons, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI). J. Math. Sci. (N.Y.), 403 190, 3, 486-495 (2013) · Zbl 1272.52003 · doi:10.1007/s10958-013-1265-1 |
| [153] | Sakai, Toshinori, Balanced convex partitions of measures in \(\mathbb{R}^2\), Graphs Combin., 18, 1, 169-192 (2002) · Zbl 1002.52002 · doi:10.1007/s003730200011 |
| [154] | Schulman, Leonard J., An equipartition of planar sets, Discrete Comput. Geom., 9, 3, 257-266 (1993) · Zbl 0779.52008 · doi:10.1007/BF02189322 |
| [155] | P. Schnider, Equipartitions with wedges and cones, 1910.13352 (2019). |
| [156] | Schnider, Patrick, Ham-sandwich cuts and center transversals in subspaces, Discrete Comput. Geom., 64, 4, 1192-1209 (2020) · Zbl 1456.52010 · doi:10.1007/s00454-020-00196-x |
| [157] | Scott, Paul R., Equipartition of convex bodies, Bull. Austral. Math. Soc., 42, 1, 141-144 (1990) · Zbl 0708.52003 · doi:10.1017/S0004972700028240 |
| [158] | Sharir, Micha, An improved bound for \(k\)-sets in four dimensions, Combin. Probab. Comput., 20, 1, 119-129 (2011) · Zbl 1211.68475 · doi:10.1017/S0963548310000143 |
| [159] | T. C. Shermer, A linear algorithm for bisecting a polygon, Information Processing Letters 41 (1992), no. 3, 135-140. · Zbl 0742.68084 |
| [160] | Simonyi, G\'{a}bor, Necklace bisection with one cut less than needed, Electron. J. Combin., 15, 1, Note 16, 5 pp. (2008) · Zbl 1163.05310 |
| [161] | Simon, Steven, Measure equipartitions via finite Fourier analysis, Geom. Dedicata, 179, 217-228 (2015) · Zbl 1348.43009 · doi:10.1007/s10711-015-0077-5 |
| [162] | Simon, Steven, Hyperplane equipartitions plus constraints, J. Combin. Theory Ser. A, 161, 29-50 (2019) · Zbl 1410.52017 · doi:10.1016/j.jcta.2018.07.012 |
| [163] | Sober\'{o}n, Pablo, Balanced convex partitions of measures in \(\mathbb{R}^d\), Mathematika, 58, 1, 71-76 (2012) · Zbl 1267.28005 · doi:10.1112/S0025579311001914 |
| [164] | Sober\'{o}n, Pablo, Gerrymandering, sandwiches, and topology, Notices Amer. Math. Soc., 64, 9, 1010-1013 (2017) · Zbl 1379.52002 · doi:10.1090/noti1582 |
| [165] | Sperner, E., Neuer beweis f\"{u}r die invarianz der dimensionszahl und des gebietes, Abh. Math. Sem. Univ. Hamburg, 6, 1, 265-272 (1928) · JFM 54.0614.01 · doi:10.1007/BF02940617 |
| [166] | Sharir, M.; Smorodinsky, S.; Tardos, G., An improved bound for \(k\)-sets in three dimensions, Discrete Comput. Geom., 26, 2, 195-204 (2001) · Zbl 1376.52046 · doi:10.1145/336154.336173 |
| [167] | Stone, A. H.; Tukey, J. W., Generalized “sandwich” theorems, Duke Math. J., 9, 356-359 (1942) · Zbl 0061.38405 |
| [168] | Solymosi, J\'{o}zsef; Tao, Terence, An incidence theorem in higher dimensions, Discrete Comput. Geom., 48, 2, 255-280 (2012) · Zbl 1253.51004 · doi:10.1007/s00454-012-9420-x |
| [169] | H. Steinhaus, A note on the ham sandwich theorem, Mathesis Polska 9 (1938), 26-28. |
| [170] | Steinhaus, Hugo, Sur la division des ensembles de l’espace par les plans et des ensembles plans par les cercles, Fund. Math., 33, 245-263 (1945) · Zbl 0061.38404 · doi:10.4064/fm-33-1-245-263 |
| [171] | Steinlein, H., Borsuk’s antipodal theorem and its generalizations and applications: a survey. Topological methods in nonlinear analysis, S\'{e}m. Math. Sup. 95, 166-235 (1985), Presses Univ. Montr\'{e}al, Montreal, QC · Zbl 0573.55003 |
| [172] | Stojmenovi\'{c}, Ivan, Bisections and ham-sandwich cuts of convex polygons and polyhedra, Inform. Process. Lett., 38, 1, 15-21 (1991) · Zbl 0736.68080 · doi:10.1016/0020-0190(91)90209-Z |
| [173] | Su, Francis Edward, Rental harmony: Sperner’s lemma in fair division, Amer. Math. Monthly, 106, 10, 930-942 (1999) · Zbl 1010.05077 · doi:10.2307/2589747 |
| [174] | Stromquist, Walter; Woodall, D. R., Sets on which several measures agree, J. Math. Anal. Appl., 108, 1, 241-248 (1985) · Zbl 0613.28003 · doi:10.1016/0022-247X(85)90021-6 |
| [175] | Steiger, William; Zhao, Jihui, Generalized ham-sandwich cuts, Discrete Comput. Geom., 44, 3, 535-545 (2010) · Zbl 1206.52008 · doi:10.1007/s00454-009-9225-8 |
| [176] | Thomas, John, A dissection problem, Math. Mag., 41, 187-191 (1968) · Zbl 0164.51502 · doi:10.2307/2689143 |
| [177] | T\'{o}th, G., Point sets with many \(k\)-sets, Discrete Comput. Geom., 26, 2, 187-194 (2001) · Zbl 0988.52028 |
| [178] | Tverberg, Helge; Vre\'{c}ica, Sini\v{s}a, On generalizations of Radon’s theorem and the ham sandwich theorem, European J. Combin., 14, 3, 259-264 (1993) · Zbl 0777.52005 · doi:10.1006/eujc.1993.1029 |
| [179] | 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. |
| [180] | Vre\'{c}ica, Sini\v{s}a T.; Zivaljevi\'{c}, Rade T., The ham sandwich theorem revisited, Israel J. Math., 78, 1, 21-32 (1992) · Zbl 0777.57011 · doi:10.1007/BF02801568 |
| [181] | Vre\'{c}ica, S. T.; Zivaljevi\'{c}, R. T., Conical equipartitions of mass distributions, Discrete Comput. Geom., 25, 3, 335-350 (2001) · Zbl 0989.52010 · doi:10.1007/s00454-001-0002-6 |
| [182] | Vre\'{c}ica, Sini\v{s}a T.; Zivaljevi\'{c}, Rade T., Arrangements, equivariant maps and partitions of measures by \(k\)-fans. Discrete and computational geometry, Algorithms Combin. 25, 829-848 (2003), Springer, Berlin · Zbl 1077.52520 · doi:10.1007/978-3-642-55566-4\_40 |
| [183] | S. T. Vre\'cica and R. T. Zivaljevi\'c, Hyperplane mass equipartition problem and the shielding functions of Ramos, 1508.01552 (2015). |
| [184] | Wagner, Uli, \(k\)-sets and \(k\)-facets. Surveys on discrete and computational geometry, Contemp. Math. 453, 443-513 (2008), Amer. Math. Soc., Providence, RI · Zbl 1149.52012 · doi:10.1090/conm/453/08810 |
| [185] | Weller, Dietrich, Fair division of a measurable space, J. Math. Econom., 14, 1, 5-17 (1985) · Zbl 0584.90016 · doi:10.1016/0304-4068(85)90023-0 |
| [186] | Willard, Dan E., Polygon retrieval, SIAM J. Comput., 11, 1, 149-165 (1982) · Zbl 0478.68060 · doi:10.1137/0211012 |
| [187] | A. Xue and P. Sober\'on, Balanced convex partitions of lines in the plane, arXiv:1910.06231 (2019); to appear in Discrete & Computational Geometry. · Zbl 1473.52029 |
| [188] | Yao, F. Frances; Dobkin, David P.; Edelsbrunner, Herbert; Paterson, Michael S., Partitioning space for range queries, SIAM J. Comput., 18, 2, 371-384 (1989) · Zbl 0675.68066 · doi:10.1137/0218025 |
| [189] | 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. |
| [190] | Yuan, Liping; Zamfirescu, Carol T.; Zamfirescu, Tudor I., Dissecting the square into five congruent parts, Discrete Math., 339, 1, 288-298 (2016) · Zbl 1322.05038 · doi:10.1016/j.disc.2015.08.009 |
| [191] | Zahl, Joshua, A Szemer\'{e}di-Trotter type theorem in \(\mathbb{R}^4\), Discrete Comput. Geom., 54, 3, 513-572 (2015) · Zbl 1329.52016 · doi:10.1007/s00454-015-9717-7 |
| [192] | Zaslavsky, Thomas, Facing up to arrangements: face-count formulas for partitions of space by hyperplanes, Mem. Amer. Math. Soc., 1, issue 1, 154, vii+102 pp. (1975) · Zbl 0296.50010 · doi:10.1090/memo/0154 |
| [193] | Zivaljevi\'{c}, Rade T., Illumination complexes, \( \delta \)-zonotopes, and the polyhedral curtain theorem, Comput. Geom., 48, 3, 225-236 (2015) · Zbl 1305.52018 · doi:10.1016/j.comgeo.2014.10.003 |
| [194] | Zivaljevi\'{c}, Rade T., Topological methods. Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., 209-224 (1997), CRC, Boca Raton, FL · Zbl 0955.52500 |
| [195] | Zivaljevi\'{c}, Rade T.; Vre\'{c}ica, Sini\v{s}a T., An extension of the ham sandwich theorem, Bull. London Math. Soc., 22, 2, 183-186 (1990) · Zbl 0709.60011 · doi:10.1112/blms/22.2.183 |
| [196] | Zivaljevi\'{c}, Rade T.; Vre\'{c}ica, Sini\v{s}a T., The colored Tverberg’s problem and complexes of injective functions, J. Combin. Theory Ser. A, 61, 2, 309-318 (1992) · Zbl 0782.52003 · doi:10.1016/0097-3165(92)90028-S |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
