RECTILINEAR DECOMPOSITIONS WITH LOW STABBING NUMBER

Let P be a rectilinear polygon. The stabbing number of a decomposition of P into rectangles is the maximum number of rectangles intersected by any axis-parallel segment that lies completely inside P. We prove t hat any simple rectilinear polygon with n vertices admits a decomposit ion with stabbing number O(log n), and we give an example of a simple retilinear polygon for which any decomposition has stabbing number Ome ga(log n). We also show that any rectilinear polygon with k greater th an or equal to 1 rectilinear holes and n vertices in total admits a de composition with stabbing number O(root k log n). When the holes are r ectangles, then a decomposition exits with stabbing number O(root k log n), which we show is tight. All of these decompositions consist of O(n) rectangles.