Convex subdivisions with low stabbing numbers (Q1046805): Difference between revisions

Consider a subdivision of the \(d\)-dimensional Euclidean space in \(n\) cells. A straight line is said to stab a convex cell if the line intersects the interior of the cell. \textit{B. Chazelle, H. Edelsbrunner and L. Guibas} showed in [Discrete Comput. Geom. 4, 139--181 (1989; Zbl 0663.68055)] that for every subdivision of the plane into \(n\) cells, there is a line that stabs \(c\cdot(\log_2n/\log_2\log_2n)\) cells, for \(n\) big enough and some constant \(c\), and this bound is best possible. In the paper under review analogous results are obtained for any dimension \(d\), \(d\geq2\). It is shown that for every subdivision of the \(d\)-dimensional Euclidean space, \(d\geq2\), into \(n\) convex cells, there is a straight line that stabs at least \(c\cdot(\log_2n/\log_2\log_2n)^{1/(d-1)}\) cells, for \(n\) big enough and some constant \(c\), and this bound is best possible.