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

Question

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!

Answer 1

Looking at this old question again, I'm now fairly convinced that the easiest route of solving this problem is using similar ideas to the one suggested by David E Speyer in a comment, namely basically setting up a integer program after some combinatorial information (like inclusion maximal sets of states that lie on a geodesic). For example if longest_geodesics is a such a set of maximal geodesics, then the following sage code will give the answer $5$.

p = MixedIntegerLinearProgram(maximization=False)
m = p.new_variable(binary=True)
for states in all_states:
    p.add_constraint(p.sum(m[line]*(1 if (states in line) else 0) 
                     for line in longest_geodesics)>=1)
p.set_objective(p.sum(m[line] for line in longest_geodesics))
p.solve()

If we assume that the set of longest_geodesics actually contained all geodesics and that the solver actually found a correct solution, then this should be a proof that it is impossible to do with $4$ geodesics. Obtaining a complete set of geodesics (or a superset thereof) could be done by finding a complete set of "forbidden triples", i.e. triples of states that do not lie on a geodesic and then build a lattice out of all sets that do not contain any forbidden triple. I took the map data cb_2018_us_state_20m.zip from this page https://www.census.gov/geographies/mapping-files/time-series/geo/carto-boundary-file.html and found a (hopefully) complete set of longest_geodesics. And in fact the integer program didn't find a solution with only $4$ great circles. Here's one with $5$:

This is using a gnomonic projections (suggested by Martin M. W. in a comment) to make all the great circles appear as line. A more conventional map would look like this:

However some people might prefer a more human checkable proof, so I provide an argument using techniques and ideas also mentioned in other answers/comments. Throughout the argument the only assumption that is made is that certain triples of states cannot lie on a great circle.

I want to show that it is impossible to cover all $50$ states with $4$ great circles. First consider the following set of states: {'Alaska', 'Delaware', 'Hawaii', 'Kentucky', 'Vermont', 'Washington'}. I claim that any three of them cannot lie on a great circle. Therefore if those $6$ states are covered by $4$ lines, either they are split $2, 2, 2$ or $1, 1, 2, 2$, since this are the only partitions of $6$ into at most $4$ parts with size of at most $3$.

First let's consider splitting {'Alaska', 'Delaware', 'Hawaii', 'Kentucky', 'Vermont', 'Washington'} into $3$ pairs, i.e. the split $2, 2, 2$. Hence we assume that $3$ great circles each cover two of those those 6 states (and potentially many more states). We proof that one more great circle is not enough to cover all states by giving a triple of states which itself cannot lie on one great circle and each state in the triple cannot lie on any of the $3$ great circles covering the pairs in the split. For each partition we first write the split and then the triple. For example

{{'Alaska', 'Delaware'}, {'Hawaii', 'Kentucky'}, {'Vermont', 'Washington'}}: {'Florida', 'South Carolina', 'Wyoming'}

means that there is no great circle through {'Florida', 'South Carolina', 'Wyoming'} and each of these three states does not lie on a great circle containing any of the three pairs. So for example {'Florida', 'Alaska', 'Delaware'} cannot lie on a great circle and the same for {'Florida', 'Hawaii', 'Kentucky'} and {'Florida', 'Vermont', 'Washington'}. Analogously for 'South Carolina' and 'Wyoming'.

{{'Alaska', 'Delaware'}, {'Hawaii', 'Kentucky'}, {'Vermont', 'Washington'}}: {'Florida', 'South Carolina', 'Wyoming'}
{{'Alaska', 'Delaware'}, {'Hawaii', 'Vermont'}, {'Kentucky', 'Washington'}}: {'Rhode Island', 'Arkansas', 'Colorado'}
{{'Alaska', 'Delaware'}, {'Hawaii', 'Washington'}, {'Kentucky', 'Vermont'}}: {'Florida', 'South Carolina', 'Wyoming'}
{{'Alaska', 'Hawaii'}, {'Delaware', 'Kentucky'}, {'Vermont', 'Washington'}}: {'Florida', 'South Carolina', 'Wyoming'}
{{'Alaska', 'Hawaii'}, {'Delaware', 'Vermont'}, {'Kentucky', 'Washington'}}: {'Louisiana', 'Rhode Island', 'New Mexico'}
{{'Alaska', 'Hawaii'}, {'Delaware', 'Washington'}, {'Kentucky', 'Vermont'}}: {'Florida', 'South Carolina', 'Wyoming'}
{{'Alaska', 'Kentucky'}, {'Delaware', 'Hawaii'}, {'Vermont', 'Washington'}}: {'Connecticut', 'New Mexico', 'Louisiana'}
{{'Alaska', 'Vermont'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'Washington'}}: {'Louisiana', 'Michigan', 'New Mexico'}
{{'Alaska', 'Washington'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'Vermont'}}: {'Connecticut', 'South Carolina', 'Minnesota'}
{{'Alaska', 'Kentucky'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Washington'}}: {'Rhode Island', 'Arkansas', 'Colorado'}
{{'Alaska', 'Kentucky'}, {'Delaware', 'Washington'}, {'Hawaii', 'Vermont'}}: {'Rhode Island', 'Arkansas', 'Colorado'}
{{'Alaska', 'Vermont'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Washington'}}: {'Florida', 'South Carolina', 'Wyoming'}
{{'Alaska', 'Washington'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Vermont'}}: see argument below
{{'Alaska', 'Vermont'}, {'Delaware', 'Washington'}, {'Hawaii', 'Kentucky'}}: {'Florida', 'South Carolina', 'Wyoming'}
{{'Alaska', 'Washington'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Kentucky'}}: {'Rhode Island', 'Iowa', 'North Dakota'}

For the split {{'Alaska', 'Washington'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Vermont'}}, we first notice that 'Connecticut' and 'South Carolina' can't lie on any of the three great circles going through the three pairs in the split, therefore the $4$th great circle has to contain both of those. Then we look at 'Indiana' and 'Tennessee': the following triples cannot lie on a great circle:

{'Indiana', 'Washington', 'Alaska'}
{'Indiana', 'Hawaii', 'Vermont'}
{'Indiana', 'Connecticut', 'South Carolina'}
{'Tennessee', 'Washington', 'Alaska'}
{'Tennessee', 'Hawaii', 'Vermont'}
{'Tennessee', 'Connecticut', 'South Carolina'}

Therefore both 'Indiana' and 'Tennessee' must lie on the great circle containing 'Delaware' and 'Kentucky', and a contradiction is reached because the triple {'Tennessee', 'Indiana', 'Delaware'} does not lie on a great circle.

Second let's consider splitting {'Alaska', 'Delaware', 'Hawaii', 'Kentucky', 'Vermont', 'Washington'} into $4$ non-empty parts, i.e. splits of the type $1, 1, 2, 2$. Here we assume that $4$ great circles cover those $6$ states (and potentially many more states). We now consider all possible such partition (there are 45). For some of these partitions we prove that they are impossible to complete by giving a triple of states that have the following properties:

1. Each of the three states in the triple does not lie on a great circle going through any of the two parts with two elements.
2. The three states in the triple cannot lie on one great circle.
3. Each combination of two states from the triple cannot lie on the great circle through each of the two parts with one element.

From (1) it follows that the three states have to be assigned to the two parts with one element. Not all them can go to only one of them because of (2). But splitting "$3$" into two nonempty parts leaves one part with $2$ elements and this lead to a contradiction by (3). Take for example

{{'Alaska', 'Delaware'}, {'Hawaii', 'Kentucky'}, {'Vermont'}, {'Washington'}}: {'Rhode Island', 'South Carolina', 'Arkansas'}

We have (1) because 'Rhode Island' cannot lie on the great circle through {'Alaska', 'Delaware'} nor {'Hawaii', 'Kentucky'} and analogously for 'South Carolina' and 'Arkansas'. We have (2) because {'Rhode Island', 'South Carolina', 'Arkansas'} cannot lie on a great circle. We have (3) because now matter what combination of two states you take from {'Rhode Island', 'South Carolina', 'Arkansas'}, this pair cannot lie on a great circle with 'Vermont' nor 'Washington'. Here's the list of all the partitions we can exlcude with that argument:

{{'Alaska', 'Delaware'}, {'Hawaii', 'Kentucky'}, {'Vermont'}, {'Washington'}}: {'Rhode Island', 'South Carolina', 'Arkansas'}
{{'Alaska', 'Delaware'}, {'Hawaii', 'Vermont'}, {'Kentucky'}, {'Washington'}}: {'Rhode Island', 'Arizona', 'Florida'}
{{'Alaska', 'Delaware'}, {'Hawaii'}, {'Kentucky', 'Vermont'}, {'Washington'}}: {'Utah', 'South Carolina', 'Florida'}
{{'Alaska', 'Delaware'}, {'Hawaii', 'Washington'}, {'Kentucky'}, {'Vermont'}}: {'Arizona', 'Louisiana', 'Wyoming'}
{{'Alaska', 'Delaware'}, {'Hawaii'}, {'Kentucky', 'Washington'}, {'Vermont'}}: {'Louisiana', 'Oklahoma', 'Connecticut'}
{{'Alaska', 'Hawaii'}, {'Delaware', 'Vermont'}, {'Kentucky'}, {'Washington'}}: {'Arizona', 'Rhode Island', 'Wyoming'}
{{'Alaska', 'Hawaii'}, {'Delaware'}, {'Kentucky', 'Vermont'}, {'Washington'}}: {'Arizona', 'Rhode Island', 'Wyoming'}
{{'Alaska', 'Hawaii'}, {'Delaware', 'Washington'}, {'Kentucky'}, {'Vermont'}}: {'Arizona', 'Louisiana', 'Wyoming'}
{{'Alaska', 'Hawaii'}, {'Delaware'}, {'Kentucky', 'Washington'}, {'Vermont'}}: {'Arkansas', 'Michigan', 'Connecticut'}
{{'Alaska', 'Hawaii'}, {'Delaware'}, {'Kentucky'}, {'Vermont', 'Washington'}}: {'Arizona', 'Louisiana', 'Wyoming'}
{{'Alaska'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'Vermont'}, {'Washington'}}: {'New Mexico', 'Michigan', 'Florida'}
{{'Alaska'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'Washington'}, {'Vermont'}}: {'Oklahoma', 'Wisconsin', 'Connecticut'}
{{'Alaska', 'Kentucky'}, {'Delaware', 'Washington'}, {'Hawaii'}, {'Vermont'}}: {'Louisiana', 'Oklahoma', 'Rhode Island'}
{{'Alaska', 'Kentucky'}, {'Delaware'}, {'Hawaii', 'Washington'}, {'Vermont'}}: {'Arizona', 'Louisiana', 'Wyoming'}
{{'Alaska', 'Vermont'}, {'Delaware'}, {'Hawaii', 'Kentucky'}, {'Washington'}}: {'South Carolina', 'Michigan', 'Arkansas'}
{{'Alaska', 'Washington'}, {'Delaware'}, {'Hawaii', 'Kentucky'}, {'Vermont'}}: {'Iowa', 'Connecticut', 'North Dakota'}
{{'Alaska'}, {'Delaware', 'Washington'}, {'Hawaii', 'Kentucky'}, {'Vermont'}}: {'Rhode Island', 'South Carolina', 'Arkansas'}
{{'Alaska', 'Vermont'}, {'Delaware'}, {'Hawaii', 'Washington'}, {'Kentucky'}}: {'Arizona', 'Louisiana', 'Wyoming'}
{{'Alaska', 'Vermont'}, {'Delaware'}, {'Hawaii'}, {'Kentucky', 'Washington'}}: {'Louisiana', 'Oklahoma', 'Wisconsin'}
{{'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Washington'}, {'Kentucky'}}: {'Rhode Island', 'Arizona', 'South Dakota'}
{{'Alaska'}, {'Delaware', 'Washington'}, {'Hawaii', 'Vermont'}, {'Kentucky'}}: {'Rhode Island', 'Arizona', 'Florida'}
{{'Alaska'}, {'Delaware', 'Washington'}, {'Hawaii'}, {'Kentucky', 'Vermont'}}: {'Utah', 'South Carolina', 'Florida'}
{{'Alaska'}, {'Delaware'}, {'Hawaii', 'Washington'}, {'Kentucky', 'Vermont'}}: {'Rhode Island', 'Arizona', 'South Dakota'}

For the rest of these partitions, we consider a pair such that

1. Each state the pair does not lie on a great circle going through any of the two parts with two elements.
2. The two states in the pair cannot lie on a great circle together with any of the two part with one element.

Therefore the two states in the pair have to be distributed on the two parts with one element one way or the other. We list both possible ways and the resulting partitions of the $8$ states into $4$ great circles with at least $2$ elements. Then we proof that this partition cannot be completed in either of the following two ways:

• (a) Giving a single state which cannot lie in a great circle with any of its parts
• (b) Giving three states which cannot lie in a great circle, but have to lie in one of the parts. (Which part can be seen because one of the three states will already be a state in the corresponding part).

Let's take as an example {{'Alaska', 'Kentucky'}, {'Delaware', 'Hawaii'}, {'Vermont'}, {'Washington'}}. Here a pair would be ('Arkansas', 'Rhode Island'). We have (1) because each triple {'Arkansas', 'Alaska', 'Kentucky'}, {'Arkansas', 'Delaware', 'Hawaii'}, {'Rhode Island', 'Alaska', 'Kentucky'} and {'Rhode Island', 'Delaware', 'Hawaii'} cannot lie on a great circle and we have (2) because {'Arkansas', 'Rhode Island', 'Vermont'} and {'Arkansas', 'Rhode Island', 'Washington'} cannot lie on a great circle. Hence we consider the two partitions where 'Arkansas' and 'Rhode Island' are paired with 'Vermont' and 'Washington'. For the candidate

[{'Kentucky', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Arkansas', 'Vermont'}, {'Washington', 'Rhode Island'}]

we are in case (b). Each of 'Florida' and 'South Carolina' cannot lie in any of the great circles given by {'Delaware', 'Hawaii'}, {'Arkansas', 'Vermont'} or {'Washington', 'Rhode Island'} Therefore they must both lie on the great circle going through {'Kentucky', 'Alaska'}, but this is a contradiction since {'Florida', 'South Carolina', 'Alaska'} cannot lie on a common great circle. For the candidate

[{'Kentucky', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Rhode Island', 'Vermont'}, {'Washington', 'Arkansas'}]

we are in case (a): the state 'New Mexico' cannot lie in a great circles going any of the pairs in the candidate. Here's list of all but one of the remaining partitions of the $6$ states into $4$ with proofs as described above:

{{'Alaska', 'Delaware'}, {'Hawaii'}, {'Kentucky'}, {'Vermont', 'Washington'}}: ('Wyoming', 'Arizona')
 [{'Delaware', 'Alaska'}, {'Hawaii', 'Wyoming'}, {'Kentucky', 'Arizona'}, {'Washington', 'Vermont'}]: Mississippi
 [{'Delaware', 'Alaska'}, {'Hawaii', 'Arizona'}, {'Kentucky', 'Wyoming'}, {'Washington', 'Vermont'}]: Connecticut


{{'Alaska', 'Hawaii'}, {'Delaware', 'Kentucky'}, {'Vermont'}, {'Washington'}}: ('Michigan', 'South Carolina')
 [{'Hawaii', 'Alaska'}, {'Delaware', 'Kentucky'}, {'Michigan', 'Vermont'}, {'Washington', 'South Carolina'}]: Florida
 [{'Hawaii', 'Alaska'}, {'Delaware', 'Kentucky'}, {'South Carolina', 'Vermont'}, {'Washington', 'Michigan'}]: Wyoming


{{'Alaska', 'Kentucky'}, {'Delaware', 'Hawaii'}, {'Vermont'}, {'Washington'}}: ('Arkansas', 'Rhode Island')
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Arkansas', 'Vermont'}, {'Washington', 'Rhode Island'}]: ['Florida', 'South Carolina', 'Alaska']
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Rhode Island', 'Vermont'}, {'Washington', 'Arkansas'}]: New Mexico


{{'Alaska', 'Vermont'}, {'Delaware', 'Hawaii'}, {'Kentucky'}, {'Washington'}}: ('New Mexico', 'South Dakota')
 [{'Alaska', 'Vermont'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'New Mexico'}, {'Washington', 'South Dakota'}]: Louisiana
 [{'Alaska', 'Vermont'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'South Dakota'}, {'Washington', 'New Mexico'}]: Michigan


{{'Alaska', 'Washington'}, {'Delaware', 'Hawaii'}, {'Kentucky'}, {'Vermont'}}: ('North Dakota', 'Connecticut')
 [{'Washington', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'North Dakota'}, {'Connecticut', 'Vermont'}]: ['Louisiana', 'New Mexico', 'Alaska']
 [{'Washington', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'Connecticut'}, {'Vermont', 'North Dakota'}]: South Carolina


{{'Alaska'}, {'Delaware', 'Hawaii'}, {'Kentucky'}, {'Vermont', 'Washington'}}: ('North Carolina', 'Connecticut')
 [{'North Carolina', 'Alaska'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'Connecticut'}, {'Washington', 'Vermont'}]: ['Delaware', 'Kansas', 'Wyoming']
 [{'Alaska', 'Connecticut'}, {'Delaware', 'Hawaii'}, {'Kentucky', 'North Carolina'}, {'Washington', 'Vermont'}]: ['Oklahoma', 'North Carolina', 'South Dakota']


{{'Alaska', 'Kentucky'}, {'Delaware', 'Vermont'}, {'Hawaii'}, {'Washington'}}: ('Arkansas', 'Rhode Island')
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Arkansas'}, {'Washington', 'Rhode Island'}]: Wyoming
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Rhode Island'}, {'Washington', 'Arkansas'}]: New Mexico


{{'Alaska', 'Kentucky'}, {'Delaware'}, {'Hawaii', 'Vermont'}, {'Washington'}}: ('Arkansas', 'Rhode Island')
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Arkansas'}, {'Hawaii', 'Vermont'}, {'Washington', 'Rhode Island'}]: Kansas
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Rhode Island'}, {'Hawaii', 'Vermont'}, {'Washington', 'Arkansas'}]: New Mexico


{{'Alaska', 'Kentucky'}, {'Delaware'}, {'Hawaii'}, {'Vermont', 'Washington'}}: ('Oklahoma', 'Connecticut')
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Oklahoma'}, {'Hawaii', 'Connecticut'}, {'Washington', 'Vermont'}]: Louisiana
 [{'Kentucky', 'Alaska'}, {'Delaware', 'Connecticut'}, {'Oklahoma', 'Hawaii'}, {'Washington', 'Vermont'}]: Wyoming


{{'Alaska', 'Vermont'}, {'Delaware', 'Kentucky'}, {'Hawaii'}, {'Washington'}}: ('Michigan', 'South Carolina')
 [{'Alaska', 'Vermont'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Michigan'}, {'Washington', 'South Carolina'}]: Florida
 [{'Alaska', 'Vermont'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'South Carolina'}, {'Washington', 'Michigan'}]: Wyoming


{{'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Vermont'}, {'Washington'}}: ('North Carolina', 'Connecticut')
 [{'North Carolina', 'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Vermont'}, {'Washington', 'Connecticut'}]: ['Delaware', 'Oklahoma', 'Louisiana']
 [{'Alaska', 'Connecticut'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Vermont'}, {'Washington', 'North Carolina'}]: Florida


{{'Alaska', 'Washington'}, {'Delaware', 'Kentucky'}, {'Hawaii'}, {'Vermont'}}: ('Michigan', 'South Carolina')
 [{'Washington', 'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Michigan'}, {'South Carolina', 'Vermont'}]: ['Iowa', 'North Dakota', 'Hawaii']
 [{'Washington', 'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'South Carolina'}, {'Michigan', 'Vermont'}]: Connecticut


{{'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Washington'}, {'Vermont'}}: ('Iowa', 'Connecticut')
 [{'Iowa', 'Alaska'}, {'Delaware', 'Kentucky'}, {'Washington', 'Hawaii'}, {'Connecticut', 'Vermont'}]: Michigan
 [{'Alaska', 'Connecticut'}, {'Delaware', 'Kentucky'}, {'Washington', 'Hawaii'}, {'Iowa', 'Vermont'}]: South Carolina


{{'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii'}, {'Vermont', 'Washington'}}: ('North Carolina', 'Connecticut')
 [{'North Carolina', 'Alaska'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'Connecticut'}, {'Washington', 'Vermont'}]: ['Delaware', 'Oklahoma', 'Louisiana']
 [{'Alaska', 'Connecticut'}, {'Delaware', 'Kentucky'}, {'Hawaii', 'North Carolina'}, {'Washington', 'Vermont'}]: Wyoming


{{'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Kentucky'}, {'Washington'}}: ('Arkansas', 'Rhode Island')
 [{'Arkansas', 'Alaska'}, {'Delaware', 'Vermont'}, {'Kentucky', 'Hawaii'}, {'Washington', 'Rhode Island'}]: ['Hawaii', 'New Mexico', 'Ohio']
 [{'Rhode Island', 'Alaska'}, {'Delaware', 'Vermont'}, {'Kentucky', 'Hawaii'}, {'Washington', 'Arkansas'}]: Michigan


{{'Alaska'}, {'Delaware'}, {'Hawaii', 'Kentucky'}, {'Vermont', 'Washington'}}: ('Connecticut', 'Arkansas')
 [{'Alaska', 'Connecticut'}, {'Delaware', 'Arkansas'}, {'Kentucky', 'Hawaii'}, {'Washington', 'Vermont'}]: South Carolina
 [{'Arkansas', 'Alaska'}, {'Delaware', 'Connecticut'}, {'Kentucky', 'Hawaii'}, {'Washington', 'Vermont'}]: ['Hawaii', 'New Mexico', 'Ohio']


{{'Alaska', 'Vermont'}, {'Delaware', 'Washington'}, {'Hawaii'}, {'Kentucky'}}: ('Wyoming', 'Arizona')
 [{'Alaska', 'Vermont'}, {'Washington', 'Delaware'}, {'Hawaii', 'Wyoming'}, {'Kentucky', 'Arizona'}]: Mississippi
 [{'Alaska', 'Vermont'}, {'Washington', 'Delaware'}, {'Hawaii', 'Arizona'}, {'Kentucky', 'Wyoming'}]: ['Maine', 'Connecticut', 'Alaska']


{{'Alaska', 'Washington'}, {'Delaware', 'Vermont'}, {'Hawaii'}, {'Kentucky'}}: ('North Dakota', 'Rhode Island')
 [{'Washington', 'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'North Dakota'}, {'Kentucky', 'Rhode Island'}]: Iowa
 [{'Washington', 'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Rhode Island'}, {'Kentucky', 'North Dakota'}]: ['Oklahoma', 'Washington', 'Arizona']


{{'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii'}, {'Kentucky', 'Washington'}}: ('Arkansas', 'Rhode Island')
 [{'Arkansas', 'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Rhode Island'}, {'Washington', 'Kentucky'}]: New Mexico
 [{'Rhode Island', 'Alaska'}, {'Delaware', 'Vermont'}, {'Hawaii', 'Arkansas'}, {'Washington', 'Kentucky'}]: Michigan


{{'Alaska', 'Washington'}, {'Delaware'}, {'Hawaii', 'Vermont'}, {'Kentucky'}}: see argument below

{{'Alaska'}, {'Delaware'}, {'Hawaii', 'Vermont'}, {'Kentucky', 'Washington'}}: ('Arkansas', 'Rhode Island')
 [{'Arkansas', 'Alaska'}, {'Delaware', 'Rhode Island'}, {'Hawaii', 'Vermont'}, {'Washington', 'Kentucky'}]: New Mexico
 [{'Rhode Island', 'Alaska'}, {'Delaware', 'Arkansas'}, {'Hawaii', 'Vermont'}, {'Washington', 'Kentucky'}]: Colorado


{{'Alaska', 'Washington'}, {'Delaware'}, {'Hawaii'}, {'Kentucky', 'Vermont'}}: ('Michigan', 'South Carolina')
 [{'Washington', 'Alaska'}, {'Delaware', 'Michigan'}, {'Hawaii', 'South Carolina'}, {'Kentucky', 'Vermont'}]: Rhode Island
 [{'Washington', 'Alaska'}, {'Delaware', 'South Carolina'}, {'Hawaii', 'Michigan'}, {'Kentucky', 'Vermont'}]: ['Washington', 'New Mexico', 'Kansas']

For the only remaining partition, namely {{'Alaska', 'Washington'}, {'Delaware'}, {'Hawaii', 'Vermont'}, {'Kentucky'}} we provide the following ad-hoc argument: We use the fact that following states cannot lie on the great circles through any of the the part {'Alaska', 'Washington'} nor {'Hawaii', 'Vermont'}:

['South Carolina', 'West Virginia', 'Tennessee', 'Illinois', 'Rhode Island']. 

Therefore 'South Carolina' must either lie on a great circle with 'Delaware' or 'Kentucky'. Assume 'South Carolina' and 'Delaware' lie on a great circle with 'Delaware'. On this great circle we cannot also have any of 'West Virginia', 'Tennessee' and 'Illinois', which therefore must lie on the great circle through 'Kentucky', but this is a contradiction, since 'West Virginia', 'Tennessee' and 'Illinois' cannot lie on a great circle. Therefore 'South Carolina' has to lie on the same great circle as Kentucky. Since 'Rhode Island' does not lie on a great circle with 'Kentucky' and 'South Carolina', we have to assume that it lies on the same great circle as 'Delaware', which leaves us with the following partition:

[{'Alaska', 'Washington'}, {'Delaware', 'Rhode Island'}, {'Hawaii', 'Vermont'}, {'Kentucky', 'South Carolina'}],

which can be seen to be absurd with the method described above by considering ['Arkansas', 'New Mexico', 'Washington'], i.e. both 'Arkansas' and 'New Mexico' can only lie on the part with 'Alaska', but at the same time cannot lie on a great circle with it.

This now got a little longer that I expected; I do like the proof using integer programming better.

Answer 2

It is known to be NP-hard to cover regions (or even just points) with a minimum number of lines. For the Euclidean plane, see Megiddo, Nimrod and Tamir, Arie (1982), "On the complexity of locating linear facilities in the plane", Oper. Res. Lett. 1 (5): 194–197, doi:10.1016/0167-6377(82)90039-6. Their construction is flexible enough that, at least for the region version, it should extend to the approximations to Euclidean geometry that one gets in small patches of spherical geometry.

Answer 3

I think the easiest route to a lower bound is to pick four states such as Hawaii, Alaska, Rhode Island, and Florida, and show that any geodesics cutting them leave too many states uncovered, or are five or more in number. It should be possible to enumerate the maximal cutting geodesics for each pair of states, and then argue using such numbers. Even trying all combinations of four cutting geodesics involving more than six states should be tractable, say on order of 10^15 combinations or so.

Answer 4

Here is a suggestion following the idea of the original poster to show for the given instance that four is too low a bound. Assume that four geodesics suffice and aim for a contradiction as follows:

Consider five states sharing or almost sharing a common longitude, e.g. the five states north of Texas or those north of and including Louisiana. One geodesic has to run through at least two of them. It should be easy to prove by hand that no four geodesics can both cover the lower 48 states and have one geodesic cover three of these five states, for any geodesic that covers at least three of these states has to leave many other states uncovered, including a group of four contiguous states and a few more groups of states (to be described soon). Now one needs three geodesics to cover this group of four and a few more groups, and one of the geodesics has to hit at least two out of this group of four. But after trying to cover three of this group of four, one has too many states left over with these choice of geodesics. The remaining few groups will contain states that cannot be covered by two geodesics alone.

So the plan is to start with the group of five states, consider each subset of two or more that can be covered by a geodesic, and then pick groups (ideally columns or linear arrangements) of states on either side of the given geodesic which are four or more in number, and consider the possibilities remaining when using one of three geodesics to cover two or more of the four states. When all these possibilities are considered, one may find five or more states left over which form a complete graph on five points in the hypergraph of geodesic relationships. Indeed, for most subsets of the initial five states north of Texas, many of those geodesics do not hit Michigan, Ohio, West Virginia, or Virginia. Of those that do hit one of those four states, they will not hit Kentucky, Tennessee, Georgia, or Florida.

By careful analysis of the states uncovered from considering the first five states, it should be possible to choose wisely two or three candidate sets of four states. For each of these candidate, one should be able to come up with five or more states not coverable by two geodesics.

Gerhard "Another Economical Use Of Pentagrams" Paseman, 2014.10.01