4
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Discrete lizard
    Apr 19, 2023 at 20:52
  • $\begingroup$ @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? $\endgroup$
    – HEKTO
    Apr 19, 2023 at 21:46
  • $\begingroup$ 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. $\endgroup$
    – Discrete lizard
    Apr 20, 2023 at 8:11
  • $\begingroup$ Wonder if this problem is complete for $\exists R$. $\endgroup$
    – rus9384
    Feb 27 at 12:02

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.