Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons

M.A. Abam; B. Aronov; M.T. Berg, de; A. Khosravi Dehkordi

doi:10.1145/1998196.1998263

Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons

M.A. Abam, B. Aronov, M.T. Berg, de, A. Khosravi Dehkordi

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

340 Downloads (Pure)

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 (non-rectilinear) 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.

Original language	English
Title of host publication	Proceedings 27th Annual ACM Symposium on Computational Geometry (SoCG'11, Paris, France, June 13-15, 2011)
Place of Publication	New York NY
Publisher	Association for Computing Machinery, Inc
Pages	407-416
ISBN (Print)	978-1-4503-0682-9
DOIs	https://doi.org/10.1145/1998196.1998263
Publication status	Published - 2011

Access to Document

10.1145/1998196.1998263

Metis249131Final published version, 508 KB

Cite this

Abam, M. A., Aronov, B., Berg, de, M. T., & Khosravi Dehkordi, A. (2011). Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons. In Proceedings 27th Annual ACM Symposium on Computational Geometry (SoCG'11, Paris, France, June 13-15, 2011) (pp. 407-416). Association for Computing Machinery, Inc. https://doi.org/10.1145/1998196.1998263

@inproceedings{801e681a3e08484bab7cc6e6f5bd885c,

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

author = "M.A. Abam and B. Aronov and {Berg, de}, M.T. and {Khosravi Dehkordi}, A.",

year = "2011",

doi = "10.1145/1998196.1998263",

language = "English",

isbn = "978-1-4503-0682-9",

pages = "407--416",

booktitle = "Proceedings 27th Annual ACM Symposium on Computational Geometry (SoCG'11, Paris, France, June 13-15, 2011)",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

}

Abam, MA, Aronov, B, Berg, de, MT & Khosravi Dehkordi, A 2011, Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons. in Proceedings 27th Annual ACM Symposium on Computational Geometry (SoCG'11, Paris, France, June 13-15, 2011). Association for Computing Machinery, Inc, New York NY, pp. 407-416. https://doi.org/10.1145/1998196.1998263

Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons. / Abam, M.A.; Aronov, B.; Berg, de, M.T. et al.
Proceedings 27th Annual ACM Symposium on Computational Geometry (SoCG'11, Paris, France, June 13-15, 2011). New York NY: Association for Computing Machinery, Inc, 2011. p. 407-416.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons

AU - Abam, M.A.

AU - Aronov, B.

AU - Berg, de, M.T.

AU - Khosravi Dehkordi, A.

PY - 2011

Y1 - 2011

N2 - 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 (non-rectilinear) 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.

AB - 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 (non-rectilinear) 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.

U2 - 10.1145/1998196.1998263

DO - 10.1145/1998196.1998263

M3 - Conference contribution

SN - 978-1-4503-0682-9

SP - 407

EP - 416

BT - Proceedings 27th Annual ACM Symposium on Computational Geometry (SoCG'11, Paris, France, June 13-15, 2011)

PB - Association for Computing Machinery, Inc

CY - New York NY

ER -

Abam MA, Aronov B, Berg, de MT, Khosravi Dehkordi A. Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons. In Proceedings 27th Annual ACM Symposium on Computational Geometry (SoCG'11, Paris, France, June 13-15, 2011). New York NY: Association for Computing Machinery, Inc. 2011. p. 407-416 doi: 10.1145/1998196.1998263

Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons

Abstract

Access to Document

Fingerprint

Cite this