32
$\begingroup$

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: from what-if.xkcd.com

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!

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – S. Carnahan Sep 27 '14 at 2:37
  • 3
    $\begingroup$ @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. $\endgroup$ – Moritz Firsching Sep 27 '14 at 8:12
  • 6
    $\begingroup$ 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. $\endgroup$ – Martin M. W. Sep 27 '14 at 13:17
  • 5
    $\begingroup$ 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. $\endgroup$ – David E Speyer Oct 2 '14 at 2:29
  • 2
    $\begingroup$ 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. $\endgroup$ – Douglas Zare Oct 2 '14 at 11:58
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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