×

Convex equipartitions via equivariant obstruction theory. (English) Zbl 1305.52005

A lovely conjecture of Nandakumar and Rao from 2006 states that every convex polygon in the plane can be partitioned into any \(n\) number of convex pieces that have equal area and equal perimeter. This elegant paper settles this conjecture positively when \(n\) is a prime power. Indeed, more is accomplished, as this result is proven for partitions of \(d\)-dimensional polytopes as well.
The method of attack has three parts: First, the problem is viewed through \(S_n\)-equivariant maps on the classical configuration spaces of \(n\) distinct labeled points in the plane. Second, such configuration of points are converted to partitions using ideas from Optimal Transport, in particular, that of a generalized Voronoi diagram. Finally, a beautiful \(S_n\)-equivariant cell complex is constructed, with \(n!\) vertices and \(n!\) facets, a generalization of the Salvetti complex. These three parts are brought together, and using equivariant obstruction theory, the result is proved.

MSC:

52A10 Convex sets in \(2\) dimensions (including convex curves)
55S91 Equivariant operations and obstructions in algebraic topology
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] V. I. Arnol’d, The cohomology ring of the colored braid group, Mathematical Notes 5 (1969), 138-140. · Zbl 0277.55002 · doi:10.1007/BF01098313
[2] F. Aurenhammer, A criterion for the affine equivalence of cell complexes in ℝdand convex polyhedra in ℝd+1, Discrete & Computational Geometry 2 (1987), 49-64. · Zbl 0608.52006 · doi:10.1007/BF02187870
[3] F. Aurenhammer, F. Hoffmann and B. Aronov, Minkowski-type theorems and leastsquares partitioning, in 8th Annual Symp. Comput. Geometry (SoCG), Berlin, June 1992, ACM, 1992, pp. 350-357.
[4] F. Aurenhammer, F. Hoffmann and B. Aronov, Minkowski-type theorems and leastsquares clustering, Algorithmica 20 (1998), 61-76. · Zbl 0895.68135 · doi:10.1007/PL00009187
[5] F. Aurenhammer and R. Klein, Voronoi diagrams, in Handbook of Computational Geometry, Noth-Holland, 2000, pp. 201-290. · Zbl 0995.65024
[6] D. Ayala and R. Hepworth, Configuration spaces and Θn, Proceedings of the American Mathematical Society, to appear. http://arxiv.org/abs/1202.2806. · Zbl 1304.18013
[7] I. Bárány, P. V. M. Blagojević and A. Szűcs, Equipartitioning by a convex 3-fan, Advances in Mathematics 223 (2010), 579-593. · Zbl 1190.52001 · doi:10.1016/j.aim.2009.08.016
[8] I. Basabe, J. González, Yu. B. Rudyak and D. Tamaki, Higher topological complexity and homotopy dimension of configuration spaces of spheres, preprint, http://arxiv.org/abs/1009.1851. · Zbl 1348.55005
[9] Björner, A., Subspace arrangements, 321-370 (1994), Basel · Zbl 0844.52008
[10] A. Björner, M. Las Vergnas, B. Sturmfels, N. White and G. M. Ziegler, Oriented Matroids, Second edn., Encyclopedia of Mathematics and its Applications, Vol. 46, Cambridge University Press, Cambridge, 1993. · Zbl 0773.52001
[11] A. Björner and G. M. Ziegler, Combinatorial stratification of complex arrangements, Journal of the American Mathematical Society 5 (1992), 105-149. · Zbl 0754.52003 · doi:10.2307/2152753
[12] P. V. M. Blagojević and A. S. Dimitrijević Blagojević, Using equivariant obstruction theory in combinatorial geometry, Topology and its Applications 154 (2007), 2635-2655. · Zbl 1158.55009 · doi:10.1016/j.topol.2007.04.007
[13] P. V. M. Blagojević, W. Lück and G. M. Ziegler, Equivariant topology of configuration spaces, preprint, http://arxiv.org/abs/1207.2852.
[14] A. Borel and J. Moore, Homology theory for locally compact spaces, The Michigan Mathematical Journal 7 (1960), 137-159. · Zbl 0116.40301 · doi:10.1307/mmj/1028998385
[15] M. E. Chisholm, k-regular mappings of 2n-dimensional euclidean space, Proceedings of the American Mathematical Society 74 (1979), 187-190. · Zbl 0406.55016
[16] F. R. Cohen and J. E. Connett, A coincidence theorem related to the Borsuk-Ulam theorem, Proceedings of the American Mathematical Society 44 (1974), 218-220. · Zbl 0284.55010 · doi:10.1090/S0002-9939-1974-0331374-2
[17] F. R. Cohen and D. Handel, k-regular embeddings of the plane, Proceedings of the American Mathematical Society 72 (1978), 201-204. · Zbl 0394.55009
[18] G. E. Cooke and R. L. Finney, Homology of Cell Complexes, Mathematical Notes, Princeton University Press, Princeton, NJ, 1967. · Zbl 0173.25701
[19] C. de Concini and M. Salvetti, Cohomology of Coxeter groups and Artin groups, Mathematical Research Letters 7 (2000), 213-232. · Zbl 0972.20030
[20] P. Deligne, Les immeubles des groupes de tresses généralisés, Inventiones Mathematicae 17 (1972), 273-302. · Zbl 0238.20034
[21] T. tom Dieck, Transformation Groups, de Gruyter Studies in Mathematics, Vol. 8, Walter de Gruyter, Berlin, 1987. · Zbl 0611.57002
[22] A. Dold, Simple proofs of some Borsuk-Ulam results, Contemporary Mathematics 19 (1983), 65-69. · Zbl 0521.55002
[23] Evans, L. C., Partial differential equations and Monge-Kantorovich mass transfer, 65-126 (2001), Boston, MA · Zbl 0954.35011
[24] R. Fox and L. Neuwirth, The braid groups, Mathematica Scandinavica 10 (1962), 119-126. · Zbl 0117.41101
[25] D. B. Fuks, Cohomologies of the braid groups mod 2, Functional Analysis and its Applications 4 (1970), 143-151. · Zbl 0222.57031
[26] D. Geiss, R. Klein, R. Penninger and G. Rote, Optimally solving a transportation problem using Voronoi diagrams, Computational Geometry, Theory and Applications, special issue for the 28-th European Workshop on Computational Geometry (EuroCG’12), Vol. 46, 2013, pp. 1009-1016. http://arxiv.org/abs/1206.3057 · Zbl 1282.49039
[27] I. M. Gelfand, M. M. Kapranov and A. V. Zelevinsky, Discriminants, Resultants, and Multidimensional Determinants, Birkhäuser, Boston, 1994. · Zbl 0827.14036
[28] C. Giusti and D. Sinha, Fox-Neuwirth cell structures and the cohomology of the symmetric group, pub. del Centro de Giorgi, to appear. http://arxiv.org/abs/1110.4137. · Zbl 1282.20058
[29] M. Goresky and R. D. MacPherson, Stratified Morse Theory, Ergebnisse der Mathematikund ihrer Grenzgebiete, Vol. 14, Springer-Verlag, Berlin, 1988. · Zbl 0639.14012
[30] A. Hubard and B. Aronov, Convex equipartitions of volume and surface area, preprint, http://arxiv.org/abs/1306.2741. Published as R. Karaser, A.Hubard and B. Arnov, Convex Equipartitions: The Spicy Chicken Theorem, Geometriae Dedicata, online July 2013. · Zbl 1301.52010
[31] H. Joris, C. Oestreicher and J. Steinig, The greatest common divisor of certain sets of binomial coefficients, Journal of Number Theory 21 (1985), 101-119. · Zbl 0574.10003
[32] L. V. Kantorovich, A new method of solving some classes of extremal problems, Doklady Akademii Nauk SSSR 28 (1940), 211-214. · Zbl 0024.32501
[33] G. Kaplan and D. Levy, GCD of truncated rows in Pascal’s triangle, Integers. Electronic Journal of Combinatorial Number Theory 4 (2004), p. #A14. http://www.emis.de/journals/INTEGERS/papers/e14/e14.pdf. · Zbl 1093.11011
[34] R. N. Karasev, Equipartition of several measures, preprint, http://arxiv.org/abs/1011.4762. · Zbl 0406.55016
[35] M. Lazard, Sur les groupes de Lie formels à un paramètre, Bulletin de la Société Mathématique de France 83 (1955), 251-274. · Zbl 0068.25703
[36] J. Matoušek, Using the Borsuk-Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry, Universitext, Springer, Heidelberg 2003; second printing, 2008. · Zbl 1016.05001
[37] J. Milnor, Collected Papers, Vol. III: Differential Topology, American Mathematical Society, Providence, RI, 2007. · Zbl 1122.01020
[38] J. Milnor and J. D. Stasheff, Characteristic Classes, Annals of Mathematics Studies, Vol. 76, Princeton University Press, Princeton, NJ, 1974. · Zbl 0298.57008
[39] H. Minkowski, Allgemeine Lehrsätze über konvexe Polyeder, Nachrichten von der Könglichen Gesellschaft der Wissenschaften zu Göttingen (1897), 198-219. Reprinted in Gesammelte Abhandlungen II (Leipzig and Berlin, 1911) 103-121.
[40] H. Minkowski, Volumen und Oberfläche, Mathematische Annalen 57 (1903), 447495. Reprinted in Gesammelte Abhandlungen II (Leipzig and Berlin, 1911) 230276.
[41] J. R. Munkres, Elements of Algebraic Topology, Addison-Wesley, Menlo Park, CA, 1984. · Zbl 0673.55001
[42] R. Nandakumar, “Fair” partitions. Blog entry, http://nandacumar.blogspot.de/2006/09/cutting-shapes.html, September 28, 2006.
[43] R. Nandakumar and N. Ramana Rao, Fair partitions of polygons: An elementary introduction, Indian Academy of Sciences. Proceedings. Mathematical Sciences 122 (2012), 459-467. · Zbl 1260.52013
[44] S. P. Novikov, Homotopy properties of Thom complexes, Matematicheskiĭ Sbornik 57 (1962), 407-442. · Zbl 0193.51801
[45] V. V. Prasolov, Elements of Homology Theory, Graduate Studies in Mathematics, Vol. 81, American Mathrmatical Society, Providence, RI, 2007. · Zbl 1120.55001
[46] B. Ram, Common factors of \(\tfrac{{n!}} {{m!(n - m)!}}(m = 1,2,...n - 1)\), Journal of the Indian Mathematical Club 1 (1909), 39-43.
[47] M. Salvetti, Topology of the complement of real hyperplanes in ℂN, Inventiones Mathematicae 88 (1987), 603-618. · Zbl 0594.57009
[48] D. Siersma and M. van Manen, Power diagrams and applications, preprint, http://arxiv.org/abs/math/0508037. · Zbl 1206.68323
[49] C. Soulé, Secant varieties and successive minima, Journal of Algebraic Geometry 13 (2004), 323-341. · Zbl 1073.14037
[50] V. A. Vassiliev, Braid group cohomologies and algorithm complexity, Functional Analysis and its Applications 22 (1988), 182-190. · Zbl 0674.68040
[51] V. A. Vassiliev, Complements of Discriminants of Smooth Maps: Topology and Applications, Translations of Mathematical Monographs, Vol. 98, American Mathematical Society, Providence, RI, 1992. · Zbl 0762.55001
[52] C. Villani, Topics in Optimal Transportation, Graduate Studies in Mathematics, Vol. 58, American Mathematical Society, Providence, RI, 2003. · Zbl 1106.90001
[53] G. M. Ziegler, Lectures on Polytopes, Graduate Texts in Mathematics, Vol. 152, Springer-Verlag, New York, 1995; seventh updated printing 2007. · Zbl 0823.52002
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.