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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
97 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 languageEnglish
Title of host publicationProceedings 27th Annual ACM Symposium on Computational Geometry (SoCG'11, Paris, France, June 13-15, 2011)
Place of PublicationNew York NY
PublisherAssociation for Computing Machinery, Inc
Pages407-416
ISBN (Print)978-1-4503-0682-9
DOIs
Publication statusPublished - 2011

Fingerprint Dive into the research topics of 'Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons'. Together they form a unique fingerprint.

Cite this