An extension of a theorem of Yao and Yao

Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: In this paper we study

N_{d} (k)

the smallest positive integer such that any nice measure

m u

in

R^{d}

can be partitioned in

N_{d} (k)

parts of equal measure so that every hyperplane avoids at least

k

of them. A theorem of Yao and Yao cite{YY1985} states that

N_{d} (1) l e 2^{d}

. Among other results, we obtain the bounds

N_{d} (2) l e 3 c d o t 2^{d - 1}

and

N_{d} (1) g e C c d o t 2^{d / 2}

for some constant

C

. We then apply these results to a problem on the separation of points and hyperplanes.

Review text

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\).

Recommendations

Cites work

Cited in

(8)

This page was built for publication: An extension of a theorem of Yao and Yao

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2250045)