Cache Packing Issue

[ju66l3r]

bigredmed Posted: Aug 30 2004, 01:32 PM

Take a park that is 1 sq mile. You could place 100 cache points into this square (10 0.1 mile increments to a side making a 10X10 matrix).

 

geoSquid Posted: Aug 30 2004, 03:58 PM

(bigredmed @ Aug 30 2004, 01:32 PM)

Take a park that is 1 sq mile.  You could place 100 cache points into this square (10 0.1 mile increments to a side making a 10X10 matrix). 

 

Actually, you could place at least 114. Square packing is not the most efficient use of space. Try hexagonal packing of the caches.

 

cachew nut Posted: Aug 30 2004, 04:29 PM

Actually you could fit 121 in an 11 x 11 matrix. 

 

ju66l3r Posted: Aug 30 2004, 05:11 PM

 

In it, I describe the equation to be y = 3k(k+1)+1 where y is the number of geocaches that fit in a k-deep hexagon.

 

Now...you can fit more than a perfect hexagon into a square space. But building on these parameters (concentric circles with radius of 264 feet...meaning no center of any circle will come within 528 feet of another circle's center), you can fit 11 caches along a single 1 mile stretch (including both endpoints). The next hexagonal packing line above that one will contain 10 circles. You can continue alternating rows of 11 and 10 for 23 total rows. The centerline of the circles in each row is 228.63 feet from the row above and below it. That makes 5258.5 feet of the second dimension covered with circles (the remaining 21+ feet is lost space).

 

With 12 rows of 11 circles and 11 rows of 10 circles, you can have 242 caches in 1 square mile. A more complicated packing algorithm *may* yield 243.

 

cachew nut Posted: Aug 30 2004, 08:12 PM

(ju66l3r @ Aug 30 2004, 02:11 PM)

 

With 12 rows of 11 circles and 11 rows of 10 circles, you can have 242 caches in 1 square mile.  A more complicated packing algorithm *may* yield 243. 

 

Either I'm not following you, or your formula is screwed up. In a 11 x 11 matrix you can fit 121. Using your method, I could only fit 126. See the two examples below.

 

I think you meant to say 6 rows of 10 circles.

 

In other words, I can't get the 23 rows you speak of. In the examples shown, the blue box represents one square mile and the circles are 528 ft in diameter.

 

The blue boxes are the same size, but the lower photo is slightly larger, thus it appears bigger.

 

Fireman78 Posted: Aug 30 2004, 09:15 PM

You guys are killing me with your math issues ROTFLOL

Edited August 31, 2004 by ju66l3r

[ju66l3r]

Ok, went back and checked my numbers...instead of drawing everything out, I was working from theory and edumacation on the back of an envelope (literally).

 

For three circles (1 in one row, 2 in the next), you can draw an equilateral triangle between centers and determine the "row height" between rows by bisecting the triangle and determining the bisectors length with the pythagorean theorem (a^2+b^2=c^2...where A is the radius, C is 2xradius, B is bisector length). When I did it the first time, I was also looking at the fact that C is half of A and determined that pythagorean in this case could be simplified to 3/4(B^2)=C^2...at which point I only plugged the radius (264) into C...instead of 2r....doh. This yielded a row height of 228 which gives 23 total rows in a mile (of which you would put 1 more row of the larger number (11)....for 242 caches...

 

Aside from whether that number sounded right or not, I should have realized that the row height had to be closer to 528 than 264 because of the fact that it's bisecting an equilateral triangle of S=528. The new row-height I get now is 457 which gives just a bit more than 11.5 rows which means a 12th row of cache centers will fit (as your picture shows at the top). So, we're left with 6 * 10 and 6 * 11 or 6 * 21 which is 126, and the most efficient way to pack discs (aka solid circles) into a plane.

 

Thanks for the math check.

[+The Roving Ravenstones]

WOW guys is math a hobby for you, or do you do this kind of stuff for work? I like math ,but I don't think that I would have ever stopped to do all this.

[ju66l3r]

A little of both. Math problems concerning complexity and things are interesting and a part of my work (bioinformatics). If a math puzzler comes to my attention, I like to give it a go. Optimal disc packing on various shapes is interesting.

 

/goes back to watching his automaton "ants" screensaver...

[+CO Admin]

Ok, went back and checked my numbers...instead of drawing everything out, I was working from theory and edumacation on the back of an envelope (literally).

 

For three circles (1 in one row, 2 in the next), you can draw an equilateral triangle between centers and determine the "row height" between rows by bisecting the triangle and determining the bisectors length with the pythagorean theorem (a^2+b^2=c^2...where A is the radius, C is 2xradius, B is bisector length). When I did it the first time, I was also looking at the fact that C is half of A and determined that pythagorean in this case could be simplified to 3/4(B^2)=C^2...at which point I only plugged the radius (264) into C...instead of 2r....doh. This yielded a row height of 228 which gives 23 total rows in a mile (of which you would put 1 more row of the larger number (11)....for 242 caches...

 

Aside from whether that number sounded right or not, I should have realized that the row height had to be closer to 528 than 264 because of the fact that it's bisecting an equilateral triangle of S=528. The new row-height I get now is 457 which gives just a bit more than 11.5 rows which means a 12th row of cache centers will fit (as your picture shows at the top). So, we're left with 6 * 10 and 6 * 11 or 6 * 21 which is 126, and the most efficient way to pack discs (aka solid circles) into a plane.

 

Thanks for the math check.

WOW if that was a virt, Id approve it.

 

Thanks

[+Harrald]

Nobody told me there was going to be a test!!!

 

and I hope this is just talk......please

[+Renegade Knight]

This dovetails with a cache concept I have called "Breeder Reactor". There is this land locked BLM Parcel that would be just perfect to try this entire thing out with.

[+Robespierre]

For three circles (1 in one row, 2 in the next), you can draw an equilateral triangle between centers and determine the "row height" between rows by bisecting the triangle and determining the bisectors length with the pythagorean theorem (a^2+b^2=c^2...where A is the radius, C is 2xradius, B is bisector length). When I did it the first time, I was also looking at the fact that C is half of A and determined that pythagorean in this case could be simplified to 3/4(B^2)=C^2...at which point I only plugged the radius (264) into C...instead of 2r....doh. This yielded a row height of 228 which gives 23 total rows in a mile (of which you would put 1 more row of the larger number (11)....for 242 caches...

You can dump the pythagoreum theorum and just use 30-60-90 triangles.

[ju66l3r]

For three circles (1 in one row, 2 in the next), you can draw an equilateral triangle between centers and determine the "row height" between rows by bisecting the triangle and determining the bisectors length with the pythagorean theorem (a^2+b^2=c^2...where A is the radius, C is 2xradius, B is bisector length). When I did it the first time, I was also looking at the fact that C is half of A and determined that pythagorean in this case could be simplified to 3/4(B^2)=C^2...at which point I only plugged the radius (264) into C...instead of 2r....doh. This yielded a row height of 228 which gives 23 total rows in a mile (of which you would put 1 more row of the larger number (11)....for 242 caches...

You can dump the pythagoreum theorum and just use 30-60-90 triangles.

That's true, except my brain always remembers the basics (pythagorean, etc) and then reinvents the shortcuts on the fly (30-60-90 side ratios). I hate rote memorization, preferring instead to remember the basics of the table and work on the why of the entries when I need that info. Less to remember in the end...so there's room for so much more.

[+Firefishe]

math is evil

repent while you still can

gpsus is coming

at N ** **.*** W** **.***

(coords decode psychically)

be ready

 

--Senior Coordinator, M.A.T.H. Ministries

Moving Algebra Toward Humility

 

Snickering regards from ;->,

Edited August 31, 2004 by Firefishe

[Shoobie & the Sand Crabs]

bigredmed Posted: Aug 30 2004, 01:32 PM

Take a park that is 1 sq mile. You could place 100 cache points into this square (10 0.1 mile increments to a side making a 10X10 matrix).

 

geoSquid Posted: Aug 30 2004, 03:58 PM

(bigredmed @ Aug 30 2004, 01:32 PM)

Take a park that is 1 sq mile.  You could place 100 cache points into this square (10 0.1 mile increments to a side making a 10X10 matrix). 

 

Actually, you could place at least 114. Square packing is not the most efficient use of space. Try hexagonal packing of the caches.

 

cachew nut Posted: Aug 30 2004, 04:29 PM

Actually you could fit 121 in an 11 x 11 matrix. 

 

ju66l3r Posted: Aug 30 2004, 05:11 PM

 

In it, I describe the equation to be y = 3k(k+1)+1 where y is the number of geocaches that fit in a k-deep hexagon.

 

Now...you can fit more than a perfect hexagon into a square space. But building on these parameters (concentric circles with radius of 264 feet...meaning no center of any circle will come within 528 feet of another circle's center), you can fit 11 caches along a single 1 mile stretch (including both endpoints). The next hexagonal packing line above that one will contain 10 circles. You can continue alternating rows of 11 and 10 for 23 total rows. The centerline of the circles in each row is 228.63 feet from the row above and below it. That makes 5258.5 feet of the second dimension covered with circles (the remaining 21+ feet is lost space).

 

With 12 rows of 11 circles and 11 rows of 10 circles, you can have 242 caches in 1 square mile. A more complicated packing algorithm *may* yield 243.

 

cachew nut Posted: Aug 30 2004, 08:12 PM

(ju66l3r @ Aug 30 2004, 02:11 PM)

 

With 12 rows of 11 circles and 11 rows of 10 circles, you can have 242 caches in 1 square mile.  A more complicated packing algorithm *may* yield 243. 

 

Either I'm not following you, or your formula is screwed up. In a 11 x 11 matrix you can fit 121. Using your method, I could only fit 126. See the two examples below.

 

I think you meant to say 6 rows of 10 circles.

 

In other words, I can't get the 23 rows you speak of. In the examples shown, the blue box represents one square mile and the circles are 528 ft in diameter.

 

The blue boxes are the same size, but the lower photo is slightly larger, thus it appears bigger.

 

Fireman78 Posted: Aug 30 2004, 09:15 PM

You guys are killing me with your math issues ROTFLOL

Total geek thing well i geuss thats geocaching

[+briansnat]

This thread scares me, because I have a feeling that someone might actually try it .

[+GeoKender]

Whoa!

If you stare at it long enough... it becomes 3D!

 

Hypothetically, you could also place another set of caches within the spaces that are not encircled and still not be overlapping the acceptable 528' parameter.

 

Is it the caches that have to be 528' apart or the virtual encompassing diametric boundaries that are not to be overlapping on one another?

 

Oh how I long for my silvaculture textbooks!

[+cachecows209]

This thread scares me, because I have a feeling that someone might actually try it  .

Amen my brother. Someone could hypothetically log like 1000 finds in a day likse that!!

Edited September 1, 2004 by cachecows209

[+cachew nut]

Hypothetically, you could also place another set of caches within the spaces that are not encircled and still not be overlapping the acceptable 528' parameter.

No, you couldn't. The caches, as represented by the red crosses, are 528 feet apart. It's 264 feet from the cross to the edge of the circle. Placing more caches as you suggest would place a cache closer than 1/10 of a mile to another one, which is not allowed.

[+geoSquid]

WOW guys is math a hobby for you, or do you do this kind of stuff for work? I like math ,but I don't think that I would have ever stopped to do all this.

A bit of both for me.

 

This particular problem is a bit of a bugbear. Back in public school I remember getting a question about how many can lids can be cut out of a 36"x36" piece of sheet steel if the lids are 4" diameter, and how much metal was wasted.

 

The official answer was 81.

 

My answer was something like 85, with substantially less waste, and I can remeber the teacher being unable to understand my explanation

 

As recently as a few years ago, when my wife taught math, I was correcting papers for her and came across a similar problem dealing with planting a garden. Nobody in that class got the right answer, but I counted their square packed garden as correct after explaining to my wife in detail why it was wrong.

 

once a nerd, always a nerd a guess.

[+mtn-man]

This thread scares me, because I have a feeling that someone might actually try it .

Actually, they have. That is a map of The Mall in Washington DC.

[kayaker22589]

Or nashville

[+Renegade Knight]

This thread scares me, because I have a feeling that someone might actually try it .

Workin On it...

[+Sissy-n-CR]

Ya'll are giving me a headache!

 

[+cachew nut]

Ya'll are giving me a headache!

 

Take another aspirin.

 

 

Disclaimer: Opinions given here should be considered anecdotal, and should not be considered medical advice. If you are unsure, consult your doctor.