Wikipedia:Reference desk/Archives/Mathematics/2014 November 8

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 8

How many circles to cover area of continental United States?

So I'm one of those online maps where you can enter a zip code and it will list all the company locations/stores that are within a given radius of the point you enter. On this particular map, the maximum radius you can enter is 200 miles.

I was wondering: assuming you had zip code locations for ANY point in the United States (which is not the case, as unique points do not have a 1-to-1 mapping with unique zip codes, but let's just assume they did for a moment), how many searches would you have to perform to encompass the entire continental US (no uncovered areas at all).

The Entire Continental US is 3,119,885 square miles according to Google

A Circle of 200 mile radius has an area of 126,000 square miles or so. 3,339,885 divided by 126,000 = around 26.5 circles.

My geometry is poor, but I somehow doubt you could arrange 27 of these circles onto a US map such that every point is covered by one the circles. I would think that there would be gaps between the circles shaped like little trianglish things.

So to repeat the question, what is the minimum number of circles you would need to cover the ENTIRE continental US with no gaps.--Captain Breakfast (talk) 04:48, 8 November 2014 (UTC)

Are the circles allowed to miss land (i.e. cover water), and if so, how much? How much are they allowed to overlap? The answer to these questions influences the answer. You may want to have a look at Hausdorff measure. It doesn't give the answer, and unfortunately doesn't illustrate graphically what's going on, but it still illuminates the questions a little bit. YohanN7 (talk) 07:08, 8 November 2014 (UTC)

My reply assumes that there is nothing sacred about circles of 200 miles radius. If there is something sacred about the 200 miles (or any radius), then the question may turn out to be both uninteresting and difficult so solve, since the geometrical shape of the US is quite complicated and ill-defined at the very small scale. YohanN7 (talk) 07:32, 8 November 2014 (UTC)

Yes, the circles are allowed to overlap and to go into Canada, Mexico, Ocean, whatever. Indeed, my question assumed that they HAVE to overlap to avoid the little gaps I mentioned in my question..--Captain Breakfast (talk) 09:23, 8 November 2014 (UTC)

I think you can find the correct answer by trial and error. What I am saying is that proving that you have the correct answer may be very difficult. For very large circles the problem becomes simpler. For very small circles it becomes extremely difficult. Your 200 miles may be somewhere in between, and quite uninteresting since the number 200 is arbitrary. YohanN7 (talk) 10:05, 8 November 2014 (UTC)

It's actually not arbitrary and somewhat interesting to me, because I want to know how many carefully selected ZIP codes I would have to enter into the online map I described in order to ensure the results of the searches, when combined, would encompass the entire landmass of the continental United States, with plenty of overlap, but no gaps.--Captain Breakfast (talk) 10:15, 8 November 2014 (UTC)

If I had to guess, the densest packing way to arrange circles is probably to follow a hexagonal tiling with a circle at the center of each hexagon. A hexagon that fits in a 200 mi circle has an area of about 104,000 mi^2 suggesting you can cover with about 30 circles. Dragons flight (talk) 08:25, 8 November 2014 (UTC)

Like I said, I have a poor mind at visualizing geometry so I'd probably have to sketch it out using software to see the hexagonal pattern you describe. If the the circles were inscribed in such a way, would there be no gaps in between the circles?--Captain Breakfast (talk) 09:23, 8 November 2014 (UTC)

This method will only yield an upper bound, not necessarily a minimum. YohanN7 (talk) 10:09, 8 November 2014 (UTC)

First, it is impossible to "tile" an area with circles without them overlapping or leaving gaps. What we're talking about (where overlaps are allowed but not gaps) is properly called a "covering" problem. (If gaps were allowed but not overlaps, then it would be a packing problem. A tiling problem relates to figures such as polygons that can meet with neither overlaps nor gaps.) I've just been searching for a diagram of the "hexagonal tiling" we've been talking about here, and I was surprised to be unable to find one on the web anywhere. I did find diagrams of some related configurations:

• This is the diagram for the corresponding packing problem. (Note that although you can join up centers of circles to make hexagons, you can also join them up to make triangles, so the grid can also be described as triangular.) To convert this diagram to the one we're talking about, just increase the diameter of each circle by a factor of 2/√3 (or about 1.155; that is, make each circle about 15.5% wider) so that they overlap enough to fill the gaps.
• This diagram shows how three of the circles overlap. If you continued the pattern, the overlaps would form a hexagonal pattern around the edge of each circle.
• This diagram shows circles that overlap in a similar manner but with additional circles so that the center of each circle has 6 circles meeting there, instead of being empty. Due to its artistic appeal it has a name: the "flower of life".

Anyway, this mathematical paper from 1939 proves that this arrangement is the optimal one for covering an infinite plane, and has a density of 2π√3 / 9 or about 1.209, so that about 20.9% of the area consists of overlaps. At least, that's more or less what the front page says; to read the rest of it online, you need an account.

So if the number 26.5 is computed correctly above (I presume it is, but didn't check) then you would expect to need something like 26.5×1.209 circles. That's just over 32, so you should expect to need at least 33. But to get the exact number, since the country has an irregular shape, I don't believe there's any way to get the true answer except by experimenting. --174.88.134.249 (talk) 03:14, 9 November 2014 (UTC)

Challenge accepted!

Circle covering - Hexagonal pattern

Image of hexagonal circle covering created with the following Mathematica code:

Graphics[Join[
 {Blue, Opacity[0.1]},
 Table[Disk[{Sqrt[3] (j + (1 + (-1)^i)/4), 3 i/2}], {i, 0, 6}, {j, 0, 6}],
 {Black, Opacity[1]},
 Table[Circle[{Sqrt[3] (j + (1 + (-1)^i)/4), 3 i/2}], {i, 0, 6}, {j, 0, 6}]
 ]]

-- Meni Rosenfeld (talk) 09:38, 9 November 2014 (UTC)

Thanks, I knew you could do it! :-) --174.88.134.249 (talk) 11:41, 9 November 2014 (UTC)

You quoted a datum of 3,119,885, but then used 3,339,885 in the calculation. -- Meni Rosenfeld (talk) 09:38, 9 November 2014 (UTC)

Thanks, all. That's really neat! Very useful terminology on tiling vs. packing vs. covering.--Captain Breakfast (talk) 00:05, 10 November 2014 (UTC)

One problem with that ZIP code online map system is that ZIP codes don't relate to points on the map, but rather areas. They derive some point from them, I assume, such as the centroid or probably wherever the post office is located. They then find all locations within 200 miles or whatever radius of that point. A reasonable approximation for small area ZIP codes, such as within cities. However, in rural areas the ZIP code itself might be more than 200 miles in radius, such that the method they use will not even find all points in the ZIP code, much less 200 miles from it. The ideal method would be to offset the borders of the ZIP code 200 miles, which would then give you overlaps and gaps to fix, so you can see why they don't bother with this. An intermediate method would be to use corner points and find any location within 200 miles of any corner. Not quite perfect, but a lot better than the single point method and a lot quicker than the border offset method. StuRat (talk) 01:18, 10 November 2014 (UTC)

According to http://www.npr.org/blogs/thetwo-way/2013/07/01/197623129/the-zip-code-turns-50-today-here-are-9-that-stand-out the zip code 80049 is 10,000 sq miles. But I've seen contradictory maps in how large it is. (Which appear to be whether various national forests are in it, where most people don't care)Naraht (talk) 14:51, 16 November 2014 (UTC)