Minimum stabbing problem for a set of convex polygons

Let $$S = \{P_1, P_2, ..., P_m\}$$ be a set of convex polygons in $$\mathbb R^2$$ with a total of $$n$$ vertices. Polygons are defined by ordered lists of vertices, and each vertex is represented by a pair $$(x,y)$$ of its Cartesian coordinates. Polygons may have non-empty pairwise intersections.

A convex polygon is called stabbed by a line, if there is a non-empty intersection between them. A set $$L$$ of lines is called stabbing set for the set $$S$$, if each polygon in the $$S$$ is stabbed by at least one line from the $$L$$. Find a minimum stabbing set for the set $$S$$.

Are there any algorithms (papers, research) for this problem?

This problem is related to this question on SO.

• Well, the problem is NP-hard, as it is a generalization of the NP-complete problem of covering/stabbing points by lines (see my answer here). I don't whether there is any work on approximation algorithms or heuristics, though. Apr 19, 2023 at 20:52
• @Discretelizard - thank you! A possible heuristics - find maximum number of polygons, stabbed by one line, remove them from the set, and so on. Does it make sense? Apr 19, 2023 at 21:46
• That sounds reasonable. This problem can be seen as a variant of the set cover problem, so this heuristic is basically the standard greedy algorithm for set-cover. Of course, an important difference between this problem and set cover is that the sets are not given explicitly here. In particular, you'll need to find a line stabbing a maximum number of polygons. Apr 20, 2023 at 8:11
• Wonder if this problem is complete for $\exists R$. Feb 27 at 12:02

As others have pointed out, the problem is NP-hard. The best we can expect in this case is an approximation algorithm. Set-Cover is a natural choice for this. But the main hurdle here is that the subsets are not explicitly handed out to us. If we somehow have a subset of all possible stabbings, we immediately have a $$O(\log n)$$ approximation algorithm via Set-Cover. Just iteratively pick the set covering the largest number of elements that are yet to be covered.
Observe that if there is a line $$l$$ that stabs a subset of $$S$$, we can shift/rotate the line so that it still stabs the same set. In the extermal case, we would have a line $$l'$$ that passes through two vertices of any of the two polygons it stabs. Therefore, we are to only observe $$n\choose 2$$ such lines, which would give us the required subsets for Set-Cover.