Covering and Packing of Rectilinear Subdivision
2019
We study a class of geometric covering and packing problems for bounded closed regions on the plane. We are given a set of axis-parallel line segments that induce a planar subdivision with bounded (rectilinear) faces. We are interested in the following problems.
(P1) Stabbing-Subdivision:
Stab all closed bounded faces by selecting a minimum number of points in the plane.
(P2) Independent-Subdivision:
Select a maximum size collection of pairwise non-intersecting closed bounded faces.
(P3) Dominating-Subdivision:
Select a minimum size collection of bounded faces such that every other face has a non-empty intersection (i.e., sharing an edge or a vertex) with some selected face.
We show that these problems are \(\mathsf { NP }\)-hard. We even prove that these problems are \(\mathsf { NP }\)-hard when we concentrate only on the rectangular faces of the subdivision. Further, we provide constant factor approximation algorithms for the Stabbing-Subdivision problem.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
17
References
1
Citations
NaN
KQI