Orthogonal Subdivisions with Low Stabbing Numbers

摘要

It is shown that for any orthogonal subdivision of size n in a d-dimensional Euclidean space, d ∈ N, d ≥ 2, there is an axis-parallel line that stabs at least Ω(log~(1/(d-1))n) boxes. For any integer k, 1 ≤ k < d, there is also an axis-aligned k-flat that stabs at least Ω(log~(1/[(d-1)/k]) n) boxes of the subdivision. These bounds cannot be improved.