An extension of a theorem of Yao and Yao (Q2250045): Difference between revisions

The measure \(\mu\) is called ``nice'' measure in \(\mathbb{R}^d\) if it has a continuous density function bounded away from \(O\). Denote by \(N_d(k)\) the smallest positive integer such that for any ``nice'' measure \(\mu\) there is a convex partition of \(\mathbb{R}^d\) into \(N_d(k)\) parts of equal \(\mu\)-measure so that every hyperplane avoids at least \(k\) of them. \textit{A. C. Yao} and \textit{F. F. E. Yao} [``A general approach to \(d\)-dimensional geometric queries.'' in: Proceedings of the seventeenth annual ACM symposium on theory of computing 163--168. ACM, New York (1985)] proved that \(N_d(1)\leq 2^d\). In the reviewed paper some new inequalities on \(N_d(k)\) are proved. These inequalities are \(N_d(1)\geq 2^{\frac{d}{2}-1}\), \(N_d(2)\leq 3\cdot 2^{d-1}\), and \(N_2(k)\leq 2k+2\). Also it is proved that \(\lim_{k\to\infty} \frac{N_d(k)}{k}=1\).