Brick partition problems in three dimensions

Abstract

A $d$-dimensional brick is a set $I_1\times \cdots \times I_d$ where each $I_i$ is an interval. Given a brick $B$, a brick partition of $B$ is a partition of $B$ into bricks. A brick partition ${\mathcal{P}}_d$ of a $d$-dimensional brick is $k$-piercing if every axis-parallel line intersects at least $k$ bricks in ${\mathcal{P}}_d$. Bucic et al. explicitly asked the minimum size $p(d,k)$ of a $k$-piercing brick partition of a $d$-dimensional brick. The answer is known to be $4(k-1)$ when $d=2$. Our first result almost determines $p(3,k)$. Namely, we construct a $k$-piercing brick partition of a $3$-dimensional brick with $12k-15$ parts, which is off by only $1$ from the known lower bound. As a generalization of the above question, we also seek the minimum size $s(d,k)$ of a brick partition ${\mathcal{P}}_d$ of a $d$-dimensional brick where each axis-parallel plane intersects at least $k$ bricks in ${\mathcal{P}}_d$. We resolve the question in the $3$-dimensional case by determining $s(3,k)$ for all $k$.

8 pages, 3 figures