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

Mohammad Ali Abam, Boris Aronov, Mark De Berg, Amirali Khosravi

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 27th Annual Symposium on Computational Geometry, SCG'11
    Pages407-416
    Number of pages10
    DOIs
    StatePublished - 2011
    Event27th Annual ACM Symposium on Computational Geometry, SCG'11 - Paris, France
    Duration: Jun 13 2011Jun 15 2011

    Publication series

    NameProceedings of the Annual Symposium on Computational Geometry

    Other

    Other27th Annual ACM Symposium on Computational Geometry, SCG'11
    CountryFrance
    CityParis
    Period6/13/116/15/11

    Keywords

    • Approximation algorithms
    • Computational geometry
    • Polygons
    • Rectangular decompositions
    • Stabbing number
    • Steiner triangulations

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Mathematics

    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

    Abam, M. A., Aronov, B., De Berg, M., & Khosravi, A. (2011). Approximation algorithms for computing partitions with minimum stabbing number of rectilinear and simple polygons. In Proceedings of the 27th Annual Symposium on Computational Geometry, SCG'11 (pp. 407-416). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/1998196.1998263