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 segment inside P. We present a 3-approximation algorithm for fi??nding a partition with minimum stabbing number. It is based on an algorithm that ??finds an optimal partition for histograms.
|Title of host publication||Abstracts 27th European Workshop on Computational Geometry (EuroCG 2011, Morschach, Switzerland, March 28-30, 2011)|
|Place of Publication||Zürich|
|Publication status||Published - 2011|