Equipartition of mass distributions by hyperplanes

被引:43
作者
Ramos, EA
机构
[1] Department of Computer Science, Univ. Illinois at Urbana-Champaign, Urbana
关键词
D O I
10.1007/BF02717729
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider the problem of determining the smallest dimension d = Delta(j, k) such that, for any j mass distributions in 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) greater than or equal to 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) less than or equal to j2(k-1). We are able to prove that Delta(j, k) = [j(2(k) - 1)/k] for a few pairs (j, k) ((j, 2) for j = 3 and j = 2(n) with n greater than or equal to 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) less than or equal to 5).
引用
收藏
页码:147 / 167
页数:21
相关论文
共 22 条
[1]   THE BORSUK-ULAM THEOREM AND BISECTION OF NECKLACES [J].
ALON, N ;
WEST, DB .
PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1986, 98 (04) :623-628
[2]  
[Anonymous], P ACM STOC 1985
[3]   NON-PARTITIONABLE POINT SETS [J].
AVIS, D .
INFORMATION PROCESSING LETTERS, 1984, 19 (03) :125-129
[4]   COMBINATORIAL ANTIPODAL-POINT LEMMAS [J].
COHEN, DIA .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (01) :87-91
[5]  
DOWNEY RG, 1992, STRUCT COMPL TH CONF, P36, DOI 10.1109/SCT.1992.215379
[6]   AN IDEAL-VALUED COHOMOLOGICAL INDEX THEORY WITH APPLICATIONS TO BORSUK-ULAM AND BOURGIN-YANG THEOREMS [J].
FADELL, E ;
HUSSEINI, S .
ERGODIC THEORY AND DYNAMICAL SYSTEMS, 1988, 8 :73-85
[7]  
Fan K., 1952, ANN MATH, V56, P431
[8]   BISECTION OF CIRCLE COLORINGS [J].
GOLDBERG, CH ;
WEST, DB .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1985, 6 (01) :93-106
[9]  
GRUNBAUM B, 1960, PAC J MATH, V10, P1257
[10]   SIMULTANE VIERTEILUNG ZWEIER KORPER [J].
HADWIGER, H .
ARCHIV DER MATHEMATIK, 1966, 17 (03) :274-&