@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",
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",
note = "27th Annual ACM Symposium on Computational Geometry, SCG'11 ; Conference date: 13-06-2011 Through 15-06-2011",
}