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.
|Title of host publication||Proceedings 27th Annual ACM Symposium on Computational Geometry (SoCG'11, Paris, France, June 13-15, 2011)|
|Place of Publication||New York NY|
|Publisher||Association for Computing Machinery, Inc|
|Publication status||Published - 2011|