Let  P  be a rectilinear simple polygon. The stabbing number of a partition of P into rectangles is the maximum number of rectangles stabbed by any axis-parallel line segment inside P. We present a 3-approximation algorithm for the problem of finding a partition with minimum stabbing number. It is based on an algorithm that finds an optimal partition for histograms. We also study Steiner triangulations of a simple (non-rectilinear) polygon P. Here the stabbing number is defined as the maximum number of triangles that can be stabbed by any line segment inside  P . We give an O(1)-approximation algorithm for the problem of computing a Steiner triangulation with minimum stabbing number.
['Mohammad Ali Abam', 'Boris Aronov', 'Mark de Berg', 'Amirali Khosravi']
Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons