# Designing an algorithm to choose the minimum number of sets containing line segments

Let's say we have some distinct sets each containing a number of line segments. I want to choose the minimum number of sets such that I will obtain a line from 0 to L with the largest gap being X long.

For example, let's say we have the sets A, B, and C as given below. L is 45 and X is 4.

If we take A, there is a gap from 10 to 15 that is greater than 4, and from 32 to 45. Notice that picking B covers the gap from 10 to 15, but there's still a gap between 40 to 45 so we need to pick C as well. However, we can pick C without picking B and reach our goal.

Is there any way to formulize this? If the problem was to pick the least number of segments I'd use a greedy approach but we are trying to minimize the number of sets here. I can only think of removing a set, inspecting if the goal can be met, and if so, removing another set. Maybe I can make this into a tree to see the effect of removing each set? Or is there another solution with less complexity?

Thanks

• Just an observation:The constraint on the gap is irrelevant since you can always extend each interval by $X/2$ (and shorten the endpoints by $X/2$). Oct 17, 2022 at 17:36
• Don't you mean "intervals" ?
– user16034
Oct 17, 2022 at 17:42
• I mean that you can move the left (resp. right) endpoint of each segment to the left (resp. right) by $X/2$ and simultaneously consider the line $[X/2, L-X/2]$ instead of $[0,L]$. Oct 17, 2022 at 17:46

In addition to D.W.'s answer, notice that the constraint on the gap is irrelevant since you can always extend each interval endpoint by $$X/2$$ (and shorten the endpoints of the line by $$X/2$$).
Then the problem can be reduced to set cover: create an item for each maximal (w.r.t. inclusion) sub-interval of $$[0,L]$$ that is covered by the same set of segments; each set of the set cover instance corresponds to a set of your instance and contains all items (i.e., sub-intervals) that are covered by some segment in that set.