# what-if.xkcd.com: stabbing (simply connected) regions on the 2-sphere with few geodesics

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!

• The paths in the image aren't great circles. They are what you get by moving a big pen along a great circle as the Earth rotates underneath. That is why the path along the eastern seaboard has the wrong convexity. – S. Carnahan Sep 27 '14 at 2:37
• @DavidRoberts True, and maybe even some US-states are not even path-connected because of islands. More flexible would be a partition of unity, which should adequately model disputed territories and no man's land. But then it is not quite clear what it means for a line to intersect. Or one could just go for disjoint open sets. – Moritz Firsching Sep 27 '14 at 8:12
• In the case of the US, which fits in a hemisphere, it might simplify things slightly to use gnomonic projection to reduce to the analogous problem with lines and plane regions. – Martin M. W. Sep 27 '14 at 13:17
• Here is an idea which I have put no real work into: Generate a few thousand random geodesics across the US. Discard any which contain a strict subset of the states on some other geodesic. Download an algorithm for set cover en.wikipedia.org/wiki/Set_cover_problem and solve the corresponding $48 \times 1000$ set cover problem. – David E Speyer Oct 2 '14 at 2:29
• I wonder whether there is a weight you can assign to each state so that the total weight of the set of states hit by any geodesic is less than $1/4$ of the total. Some other approaches correspond to particular sets of weights. – Douglas Zare Oct 2 '14 at 11:58