Stabbing Rectangles by Line Segments - How Decomposition Reduces the Shallow-Cell Complexity

Timothy M. Chan, Thomas C. van Dijk, Krzysztof Fleszar +2

We initiate the study of the following natural geometric optimization problem. The input is a set of axis-aligned rectangles in the plane. The objective is to find a set of horizon…