@inproceedings{86b46b6b9288447cbede36ab8e99d5c3,

title = "Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons",

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 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 (nonrectilinear) 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.",

keywords = "Approximation algorithms, Computational geometry, Polygons, Rectangular decompositions, Stabbing number, Steiner triangulations",

author = "Abam, {Mohammad Ali} and Boris Aronov and {De Berg}, Mark and Amirali Khosravi",

note = "Copyright: Copyright 2011 Elsevier B.V., All rights reserved.; 27th Annual ACM Symposium on Computational Geometry, SCG'11 ; Conference date: 13-06-2011 Through 15-06-2011",

year = "2011",

doi = "10.1145/1998196.1998263",

language = "English (US)",

isbn = "9781450306829",

series = "Proceedings of the Annual Symposium on Computational Geometry",

pages = "407--416",

booktitle = "Proceedings of the 27th Annual Symposium on Computational Geometry, SCG'11",

}