2021/01/20 by Ilkyoo Choi, Minseong Kim, Choi, Ilkyoo +3
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2101.08192
openalex publication_date 2021/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A d-dimensional brick is a set I1× ⋯ × Id where each Ii is an interval. Given a brick B, a brick partition of B is a partition of B into bricks. A brick partition Pd of a d-dimensional brick is k-piercing if every axis-parallel line intersects at least k bricks in Pd. 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 Pd of a d-dimensional brick where each axis-parallel plane intersects at least k bricks in Pd. We resolve the question in the 3-dimensional case by determining s(3, k) for all k.