Computing Conforming Partitions with Low Stabbing Number for Rectilinear Polygons
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914198637772800 |
|---|---|
| author | Biedl, Therese Durocher, Stephane Mondal, Debajyoti Nishat, Rahnuma Islam Rivier, Bastien |
| author_facet | Biedl, Therese Durocher, Stephane Mondal, Debajyoti Nishat, Rahnuma Islam Rivier, Bastien |
| contents | A conforming partition of a rectilinear n-gon P (possibly with holes) is a partition of P into rectangles without using Steiner points (i.e., all corners of all rectangles must lie on the boundary of P). The stabbing number of such a partition is the maximum number of rectangles intersected by an axis-aligned segment lying in the interior of P. In this paper, we examine the problem of computing conforming partitions with low stabbing number. We show that computing a conforming partition with stabbing number at most 4 is NP-hard, which strengthens a previously known hardness result [Durocher \& Mehrabi, Theor. Comput. Sci. 689: 157-168 (2017)] and eliminates the possibility for fixed-parameter-tractable algorithms parameterized by the stabbing number unless P = NP. In contrast, we give (i) an O(n log n)-time algorithm to decide whether a conforming partition with stabbing number 2 exists, (ii) a fixed-parameter-tractable algorithm parameterized by both the stabbing number and treewidth of the pixel graph of the polygon, and (iii) a fixed-parameter-tractable algorithm parameterized by the stabbing number for polygons without holes in general position. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_11274 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing Conforming Partitions with Low Stabbing Number for Rectilinear Polygons Biedl, Therese Durocher, Stephane Mondal, Debajyoti Nishat, Rahnuma Islam Rivier, Bastien Computational Geometry A conforming partition of a rectilinear n-gon P (possibly with holes) is a partition of P into rectangles without using Steiner points (i.e., all corners of all rectangles must lie on the boundary of P). The stabbing number of such a partition is the maximum number of rectangles intersected by an axis-aligned segment lying in the interior of P. In this paper, we examine the problem of computing conforming partitions with low stabbing number. We show that computing a conforming partition with stabbing number at most 4 is NP-hard, which strengthens a previously known hardness result [Durocher \& Mehrabi, Theor. Comput. Sci. 689: 157-168 (2017)] and eliminates the possibility for fixed-parameter-tractable algorithms parameterized by the stabbing number unless P = NP. In contrast, we give (i) an O(n log n)-time algorithm to decide whether a conforming partition with stabbing number 2 exists, (ii) a fixed-parameter-tractable algorithm parameterized by both the stabbing number and treewidth of the pixel graph of the polygon, and (iii) a fixed-parameter-tractable algorithm parameterized by the stabbing number for polygons without holes in general position. |
| title | Computing Conforming Partitions with Low Stabbing Number for Rectilinear Polygons |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2411.11274 |