In the latest what-if Randall Munroe ask for the smallest number of geodesics that intersect all regions of a map. The following shows that five paths of satellites suffice to cover the 50 states of the USA:
A similar configuration where the lines are actually great circles is claimed by the author:
They're all slightly curved, since the Earth is turning under the satellites, but it turns out that this arrangement of lines also works for the much simpler version of the question that ignores orbital motion: "How many straight (great-circle) lines does it take to intersect every state?" For both versions of the question, my best answer is a version of the arrangement above.
There has been quite some work on similar sounding problems. For stabbing (or finding transversals of) line segments see as an example Stabbing line segments by H. Edelsbrunner, H. A. Maurer, F. P. Preparata, A. L. Rosenberg, E. Welzl and D. Wood (and papers which reference it.) or L.M. Schlipf's dissertation with examples of different kinds.
Is there an algorithmic approach known to tackle this problem (or for the simpler problem when all regions of the map are convex)?
In the case of the 50 states of the USA, it is of course easy to see that one great circle does not suffice: take two states (e.g. New York and Louisiana) such that all great circles that intersect those do not pass through a third state (e.g. Alaska). Similarly one can show that we need at least 3 great circles.
Maybe it would be helpful to consider all triples of regions that do not lie on a great circle and use this hypergraph information to deduce lower bounds.
What are good methods to find lowers bounds?
Randall Munroe's conjectures that 5 is optimal:
I don't know for sure that 5 is the absolute minimum; it's possible there's a way to do it with four, but my guess is that there isn't. [...] If anyone finds a way (or proof that it's impossible) I'd love to see it!