×

Equipartition of mass distributions by hyperplanes. (English) Zbl 0843.68120

Summary: We consider the problem of determining the smallest dimension \(d = \Delta (j, k)\) such that, for any \(j\) mass distribution in \(\mathbb{R}^d\), there are \(k\) hyperplanes so that each orthant contains a fraction \(1/2^k\) of each of the masses. The case \(\Delta (1,2) = 2\) is very well known. The case \(k = 1\) is answered by the ham-sandwich theorem with \(\Delta (j,1) = j\). By using mass distributions on the moment curve the lower bound \(\Delta (j,k) \geq j (2^k - 1)/k\) is obtained. We believe this is a tight bound. However, the only general upper bound that we know is \(\Delta (j,k) \leq j2^{k - 1}\). We are able to prove that \(\Delta (j,k) = \lceil j(2^k - 1)/k \rceil \) for a few pairs \((j,k)\) \(((j,2)\) for \(j = 3\) and \(j = 2^n\) with \(n \geq 0\), and \((2,3))\), and obtain some nontrivial bounds in other cases. As an intermediate result of independent interest we prove a Borsuk-Ulam-type theorem on a product of balls. The motivation for this work was to determine \(\Delta (1,4)\) (the only case for \(j = 1\) in which it is not known whether \(\Delta (1,k) = k)\); unfortunately the approach fails to give an answer in this case (but we can show \(\Delta (1,4) \leq 5)\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Full Text: DOI

References:

[1] N. Alon and D. B. West. The Borsuk-Ulam theorem and bisection of necklaces,Proc. Amer. Math. Soc.98 (1986), 623-628. · Zbl 0614.05005 · doi:10.2307/2045739
[2] D. Avis, Non-partitionable point sets,Inform. Process. Lett.19 (1984), 125-129. · Zbl 0564.51007 · doi:10.1016/0020-0190(84)90090-5
[3] D. I. A. Cohen, On the combinatorial antipodal-point lemmas,J. Combin. Theory Ser. B,27 (1979), 87-91. · Zbl 0421.05022 · doi:10.1016/0095-8956(79)90071-6
[4] R. Downey and M. Fellows, Fixed parameter intractability (extended abstract), inProceedings of the 7th Annual IEEE Conference on Structures in Complexity Theory, 1992, pp. 36-49.
[5] E. Fadell and S. Husseini, Anideal-valued cohomological index-theory with applications to Borsuk-Ulam and Bourgin-Yang theorems,Ergodic Theory Dynamical Systems8* (1988), 73-85. · Zbl 0657.55002 · doi:10.1017/S0143385700009342
[6] K. Fan, A generalization of Tucker’s combinatorial lemma with topological applications.Ann. of Math.56 (1952), 431-437. · Zbl 0047.42004 · doi:10.2307/1969651
[7] C. H. Goldberg and D. B. West, Bisection of circle colorings,SIAM J. Algebraic Discrete Methods6 (1985) 93-106. · Zbl 0558.05008
[8] B. Grünbaum, Partitions of mass-distributions and on convex bodies by hyperplanes,Pacific J. Math.10 (1960), 1257-1261. · Zbl 0101.14603
[9] H. Hadwiger, Simultane Vierteilung zweier Körper,Arch. Math. (Basel)17 (1966), 274-278. · Zbl 0137.41501
[10] M. W. Hirsch, A proof of the nonretractibility of a cell onto its boundary,Proc. Amer. Math. Soc.14 (1963), 364-365. · Zbl 0113.16704 · doi:10.2307/2034644
[11] C.-Y. Lo, J. Matoušek, and W. Steiger, Algorithms for ham-sandwich cuts.Discrete Comput. Geom.11 (1994), 433-452. · Zbl 0806.68061 · doi:10.1007/BF02574017
[12] J. Matoušek, Efficient partition trees,Discrete Comput. Geom.8 (1992), 315-334. · Zbl 0752.68088 · doi:10.1007/BF02293051
[13] J. Matoušek, Range searching with efficient hierarchical cuttings,Discrete Comput. Geom.10 (1993), 157-182. · Zbl 0774.68101 · doi:10.1007/BF02573972
[14] J. Matoušek, Geometric Range Searching, Report B 93-09, Institute for Computer Science, Department of Mathematics, Freie Universität, Berlin, July 1993.
[15] C. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence,J. Computer System Sci.48 (1994), 498-532. · Zbl 0806.68048 · doi:10.1016/S0022-0000(05)80063-7
[16] J. P. Robinson and M. Cohn, Counting sequences,IEEE Trans. Comput.30 (1981), 17-23. · Zbl 0455.94053
[17] A. W. Tucker, Some topological properties of disk and sphere, inProceedings of the First Canadian Mathematical Congress, Montreal, 1945, pp. 285-309. · Zbl 0061.40305
[18] D. G. Wagner and J. West, Construction of uniform Gray codes,Congr. Numer.80 (1991), 217-223. · Zbl 0735.94011
[19] D. E. Willard, Polygon retrieval,SIAM J. Comput.11 (1982), 149-165. · Zbl 0478.68060 · doi:10.1137/0211012
[20] A. C. Yao and F. F. Yao, A general approach tod-dimensional geometric queries, inProceedings of the 17th ACM Annual Symposium on the Theory of Computing, 1985, pp. 163-169.
[21] F. Yao, D. Dobkin, H. Edelsbrunner, and M. Paterson, Partitioning space for range queries,SIAM J. Comput.18 (1989), 371-384. · Zbl 0675.68066 · doi:10.1137/0218025
[22] Zhong, C.; Tan, K. K. (ed.), The Borsuk-Ulam theorem on product space, 362-372 (1992), Singapore · Zbl 1427.55003
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.