Abstract
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.
Original language | English |
---|---|
Title of host publication | Abstracts 27th European Workshop on Computational Geometry (EuroCG 2011, Morschach, Switzerland, March 28-30, 2011) |
Place of Publication | Zürich |
Publisher | ETH Zürich |
Pages | 103-106 |
Publication status | Published - 2011 |