One Million Dollar Desecration Prize

For some reason my idea of a mathematically efficient packing of the stars in the American flag was not that popular. I think this is because people really want a flag where the importance of states is shown. Important states should have big stars and other loser states smaller ones.

So the problem becomes “how can you arrange these different sized circles most efficiently inside a rectangle”? This problem is NP-Hard (pdf). This mean there is no polynomial time algorithm that will put different sized circles into a rectangle and guarantee that arrangement to have the least amount of free space. If you find a way to solve this packing problem in polynomial time you win the 1 million dollar prize as this will show that P=NP

So if you can find an efficient way to desecrate the American flag you can win 1 million dollars. In my next post I will look at heuristic methods to desecrate the American flag using the number of people executed by the state since 1976 to decide the size of star the state gets on the flag.

The American flag is inefficient

America is backed by an image and symbol that is inefficient.



The stars represent the 50 states. I have no idea what the candy stripe is about it is probably an ad for a barbers or something.

Anyway is the packing of these 50 stars efficient? If you are not willing to make the symbol of your nation efficient what does that say? What can you think about a country if they are willing to waste fabric in a flag? This is fabric that adds to the cost to schools to buy a flag. This is fabric that could be used to bandage the wounds of injured puppies. So in the name of all that is efficient lets see if I can fix the flag to something less crap.

Each star is a state and they should all be equal minimum gaps between them. The current attempt at a flag does not have all neighbouring stars the same distance so I do not need to.
The stars are going to be modeled as circles (with stars in the middle) The use of circles ensures the stars will be kept a minimum distance apart.

Now you might guess that the best way to pack circles is in the hexagonal (green grocer) formation where the upper layer falls between the circles in the lower layer.
This is obviously better then a square packing.




But this is not the most efficient way to pack circles into a square.


Now the flag circle holding part is rectangular not square. Does this effect how we should pack stars into it?
For a 5*1 rectangle the hexagonal packing is still not best


How about for the 6*5 packing used in the flag?

Of course no one really thinks all states are equal. If you allow some states to have smaller stars then others you can come up with even more interesting patterns.