GPS, linear algebra, and fractals in computer graphics

Fellow math guy Bunganator called to my attention this article about the linear algebra that is used by the Global Positioning System to determine location.

My puzzle cache Where's Yoda? is a simplified version of this -- think of the data from each guess in the Yoda game as the input from one satellite. Finding Yoda's location amounts to solving the system of equations that results from the information given by each guess.

The article Bunganator sent includes a reference to a book called Linear Algebra, Geodesy, and GPS by Gilbert Strang and Kai Borre. I'll have to check this book out -- I've wondered how to incorporate GPS topics into my courses (rather than the other way 'round... Gah!) -- but I note that the first 274 pages appear to be straight linear algebra that can be found in other books, including other Gilbert Strang books that I've taught out of before. I wonder why the publisher or the author felt the need to pad out this title with a introductory linear algebra treatment that is readily available elsewhere.

---

I have a question for the computer people out there. I have a programmer friend who, in the context of 3D virtual environments, came across the term "2 1/2 dimensional space". This has a specific meaning in mathematics: the Hausdorff dimension of a set can be a non-integer when it has fractal properties. For example, a set resembling a shoreline could have a Hausdorff dimension between 1 and 2, or a set resembling the face of a mountain could have a Hausdorff dimension between 2 and 3.

I remember vaguely that there are algorithms involving fractals or randomization for realistically rendering natural features like these, but don't know much about them. Does anyone else? And, when people in 3D graphics use the term "2 1/2 dimensional", are they using it in an informal sense, or does Hausdorff dimension actually arise in the description of these rendering algorithms?

Input sought on puzzle cache series

I have a series of six caches in Highland Park in Saint Paul called Plato's Five Gems. Four of them are puzzles, one is a two-stage multi that has a puzzle at the first stage (by the way, this post by Spinowner suggests to me that I am correct, or at least justified, in classifying this one as a multi and not a puzzle), and one is a traditional.

Some recent posts on the MnGCA forums have given me an idea about this series. First, Silent Bob suggests in this post that there should be an 18 month time limit on caches. Second, pfalstad suggests in this post that hard puzzles should not be taking up space in city parks in cache-dense areas.

Some folks have had trouble with these puzzles, so I guess they're hard in some sense, and Highland Park is indeed a city park, and this series takes up a good fraction of that entire park's cache-able area.

Here's my idea: the "container" for the cache that ties them all together, Plato's Five Gems: Bunganator's Grand Slam, is a large icosahedral die, and the finder signs one of the 20 faces to log it. (See this blog post by Sokratz for a discussion on whether this is a proper cache container.) At this moment, there are 10 finders, and so there are 10 faces left to sign. I propose that when there are 20 logs on the grand slam cache, I will archive the entire series.

The only thing that gives me pause is the expectation of cache permanence in the guidelines. And I don't want to archive the series simply because some people don't do or hate or ignore puzzles. But still, it might be fun to create a sort of race for the last 10 finders, and then the icosahedral die would be a keepsake (or potential travel bug?) containing the names of 20 puzzlers.

Input welcome.

Yoda (and his blogging owner) is back in action

I need to post more often. If I wait a week, then there are so many possible topics bouncing around in my brain that I can't remember them all.

• After being disabled for a week, my puzzle cache Where's Yoda? (I like puzzles) is back in action. A couple weeks ago, after three consecutive (and compelling) DNFs I walked over to GZ from work. I saw the camouflage, but the cache container was missing. Extra disappointing because there are three TBs logged into it. I got a new container together and found a much better nearby hiding location. This cache has been doomed from the start -- allegations of malware, being banned by Blogger, container (probably) chucked into the Mississippi River -- but Yoda keeps coming back. You wouldn't expect anything less of a Jedi master.
  
• Stumbled across two Twin Cities blogs -- Sokratz and Lazy Lightning (Silent Bob's blog not just about geocaching) -- and noticed on the MnGCA forums that minnesotabrad is writing a newsletter. meralgia -- who has been keeping up with geocaching virtually but who is coming out of hibernation for hiding and finding -- told me about Sokratz's blog, and his post about cache containers caught my attention because I have a puzzle cache container (I like puzzles) that is a large polyhedral die and may have slipped through the cracks of the reviewing process. If I go out there and put it in a ziploc bag, is it OK then?
  
• Interesting discussion on the MnGCA forums about the effect of puzzle caches on the proximity guideline. I like puzzles.
  
• Shoestorm drove Bunganator and me up to Fridley Weeknight caching on Wednesday, where we met Millah for a couple pre-caching puzzles. Interesting discussion on the MnGCA forums (and here) about the integrity of puzzle solvers. I like puzzles. Also was nice to see broken_tooth, Bus&Betty, cstjohn, minnesotabrad (whom I pestered until he finally gave me his 2nd pathtag), sir_zman, MN_Cavepeople, fireman121, Red_Devil35, oneied_cooky. It was also nice to meet mall security at this cache.
  
• Finally solved Millah's fun puzzle About Time. I like puzzles.
  
• I have an important piece of the solution to Shoestorm's puzzle cache Dr. Strangecache. I like puzzles. I'll take cash offers for that piece of the solution via email.
  
• Shoestorm, Millah, and I are planning a suite of three caches about football (the beautiful game), specifically the rivalry between Manchester United (shoestorm's club) and Arsenal (mine). They'll be "unknown" caches, but not necessarily puzzles. I like puzzles. Too bad Arsenal mucked things up by almost sealing a trip to the semifinals of the Champions League with a late, late goal against Liverpool in their quarterfinal second leg, only to give it away on a B***S*** penalty about 30 seconds later.
  
• Millah and I tried to go to Cottage Grove Ravine Park last Sunday for all the Party caches, but we never got there because there were too many interesting things along the way. Maybe we'll crash that Party tomorrow.
  

April Fools!

Read the note I posted on the cache page for Millah's baseball-themed puzzle cache. Though I didn't intend it, this note had the effect (assuming that INATN counts words in notes) of pushing me back on to the list of Top Ten Wordiest Cachers in Minnesota. Once again, geocaching achievements attained by cheating...

What does "Cache our way to Illinois" mean to you?

To my family, it means "find one cache at a rest stop in Wisconsin". Really, I shouldn't expect my family to turn a 7 hour trip into a 12 hour trip so that they can sit in the car while I roam the 0.5 miles surrounding the interstate. And, the trip wasn't that bad -- I got my one Wisconsin cache and got out a couple times in the Chicago area. I'm here to report that Chicago caches are... not that different from Twin Cities Caches. Especially since we got 8 inches of snow a week ago Friday. It felt just like home.

• I'm in love with the Palm Centro, but I realized one bad thing about CacheMate -- right now, the cache information does not include the size of the container or the cache owner. It turns out that this is a MacCaching issue; when it converts the .gpx file into the .prc file for the Palm to read, it leaves out this info. The author of MacCaching promised in his forum that he would fix this.
  
• I'm enjoying TheDazzlerD's two puzzles about the tube down around Savage [edit: the puzzles are in Savage, not the tube. I mean the London Underground. No subway in Savage as far as I know.]. I'm thinking of honoring them with a sort of parody cache of my own about the Detroit mass transit train -- one loop with 12 stops. Pathetic for a metro area of that size.
  
• Enjoyed Weeknight caching on Wednesday in Burnsville. Pre-cached with Bus&Betty and the topgears. At the park near the Burnsville mall, we then met up with ThCollector, cstjohn, X51hz, speedysk1, casinoman, and brokentooth. After finding four caches and avoiding dog poop, we moved on to Chili's, where there was a great flurry of travel bug and geocoin trading and discovering. B&B took three TBs from me on their trip to MI, and I grabbed my own Alvin's Phone Line coin from TheCollector, because, although I'm glad I've released all the coins I have purchased (almost), I miss them sometimes.
  
• Congratulations to MN_Cavepeople on the birth of a mini-Caveman!
  
• On a less important note, congratulations to pfalstad and FSU*Noles on being FTF on GW's Crimson clupea harengus puzzle cache, which was unfound for a long time. No sour grapes here, but I'm finding that unless a puzzle catches my fancy like those tube caches, it starts to feel a lot like homework. Good thing that Millah is on my case all the time...
  
• As if you care, some Arsenal news: after a complete disaster at Chelsea in the league (two goals to Didier Drogba in the last 20 minutes after going up 0-1), we can kiss the league goodbye and start thinking about the Champions League -- the first leg of the quarterfinal is Wednesday against Liverpool. In fact, we play Liverpool three times in six days. Can't beat 'em three times in a row, but hope we can do enough to move on in Europe.
  
• How about Davidson? I hadn't really cared about any of the basketball, but I caught just a little of Stephen Curry's dismantling of Wisconsin last night, and now I'm a fan! I grew up in the early 80s, when NC State (1983) and Villanova (1985) were making March Madness what it is today. Davidson for the Final Four! Even though my wife's ex-boyfriend went there!
  

Are puzzle caches worth the hassle? Um... yes.

I almost swore off hiding puzzle caches this week. I aimed to publish my puzzle Anchors Aweigh!, about Navy ships and the calendar algorithm, on Leap Day, February 29. I wanted to place it in South St. Paul and pay a little tribute to Bobcam and knowschad, two area hiders whose caches I like and whose styles are very different. But I wasn't able to get out that way Thursday, so I compromised and started looking for a hiding spot near the U of M campus. pfalstad had an infamous cache called The Fun Side of the River down by the river, west of the stairs that are south of Harvard St. Finding it involved walking into a storm drain. I endangered my life trying to find that one, not realizing that it had been archived two weeks earlier. There's a big gap there now on the geogoogle map, and so I went down to that area, past the sign saying "stairs closed", slipped on ice, fell on my back, broke a tree branch that cut my nose on the way down, and eventually placed the cache in what I thought was a clever place. Done.

Here's the problem: I placed it within 200 feet of the final location of another cache. A CACHE I HAVE FOUND. Our local cache reviewer patiently explained that sometimes exceptions are made to the proximity rule if the caches are at drastically different altitudes, but not in this case because they were so close. Ugh. No Leap Day publication.

On Saturday, March 1, I was able to retrieve the cache (which got iced into what I thought was a clever location) and take it several miles away to a very peaceful, relatively muggle-free, favorite location of mine. The puzzle re-work was relatively painless.

Speaking of which, foundinthewild called me today to ask about Plato's Five Gems: Octahedron, and he mentioned that rickrich includes a coordinate offset into some/all of his puzzles, presumably so that if he has to update the coordinates, he can do so without reworking the puzzle. I'll have to consider that, because this very thing has gotten me into trouble once or twice.

In other news:

• I mailed out 50 pathtags early this week. One of them went to Kacky in Maine. That is the only trade I have initiated myself so far, because I was so impressed with and moved by the story of her pathtag: the design is in honor of her son, who is autistic and builds birdhouses from recycled materials with other autistic adult men.
  
  Kacky wrote on the pathtags forum that she mentioned the signature card that I included with my pathtag on the podcast Cachers of the Round Table, one of my favorite podcasts. Jeez, two podcast mentions in three weeks! Time for another related rates problem involving the radius of my head?
  
  
• I used the "I have to run out to the store" ruse to grab an FTF on shoestorm's first hide, a puzzle cache with an incredibly muggly final location. A well-crafted and well-thought-out hide. I hope it survives.
  

Go away, anchors! Bad anchors!

I'm planning a puzzle cache called Anchors Aweigh! So I checked to see how many geocaches have this name. The answer is 13. For fun, I checked to see how many geocaches have the name Anchors Away! The answer is 20. I decline to draw conclusions about geocachers from this. I will say that none of the Anchors Away! caches are in Minnesota. We're a smart bunch.

By the way, the cache is about ANCHORS in the context of a mathematical algorithm. Can you guess what it's about?

An embarrassment of riches in the way of geocaching social events lately: WeekNight caching in Ham Lake on Wednesday night, and Breakfast Buddies in Richfield this morning.

The highlight of the Ham Lake outing was the spectacular lunar eclipse overhead. It was also nice to hang out with topgear, Bus&Betty, and sir_zman. I hadn't met topgear before, but I had found some of his caches, so it was cool meeting him by accident at his own awesome puzzle cache ORIGAMI FLYING BIRD before the WeekNight. We all ended up at the Green Mill for dinner, but getting there was a trick. sir_zman gave me coordinates for the restaurant, but they took us both to an industrial park across the street from the complex that Green Mill is in. zman put his geo-sense to work, but I had to stop in at a Walgreens for directions before logging the dinner smiley.

Also, along the way to dinner I stopped off for a quick one, The Puck Stops Here!, another topgear cache as it turns out.

Two FTFs in the last couple days -- a poppa99 footbridge cache in Bordertown (nice meeting him at BB today), and a Bobcam puzzle cache, his first out of 85 hides. The Bobcam cache I DNFed last night with mini-bass, but I had solved the puzzle correctly. Bobcam had a little kink to work out of the puzzle (I've been there, I understand!), so I went out there again with Millah with the correct coordinates, and we still couldn't find it. A quick phone call to Bobcam produced the hint we needed, and one ripped Millah down coat later, we had our co-FTF. On to Richfield.

The Old Country Buffet was crawling with geocachers! I think the management was a little nervous, but they got our money, so it's all good. Who did I meet or talk to? I know I'll forget someone, but I'll give it a shot:

• Millah
  
• Pippin and Merry
  
• Bus&Betty
  
• topgear
  
• Bobcam
  
• knowschad
  
• sir_zman
  
• two of hearts
  
• Oneied Cooky
  
• TheCollector
  
• minnesotabrad
  
• Moe the Sleaze
  
• poppa99
  
• speedysk1
  
• RubberToes
  
• Red_Devil35
  
• Jonas
  
• GeoPierce
  

All these people to give pathtags to, and wouldn't you know it, I got a call from my wife a half-hour after the event to say that my pathtags had arrived in the mail. (Isn't it sweet that she recognized the importance of this fact?)

Congratulations to Millah on his 500th cache find -- Picture Sudoku -- which we picked up after the Breakfast Buddies event along with several others as we bumped into multiple cachers on the Traveling After Party Event Cache. We celebrated Millah's milestone with a Flat Earth Cygnus X-1 beer afterwards (we did not play Hemispheres [edit: Cygnus X-1 is on Farewell to Kings] by Rush, however). Millah gets Pathtag #1. Now, it's time to address some envelopes. Fifty pathtag trades to make good on. I turned off the trade button, but I'll be happy to trade with local cachers!

V = (4/3)*pi*r^3

Thanks to sir_zman, host of the Twin Cities Geocaching Podcast, for his kind words about this blog in his 2/18/08 podcast. Since he mentioned the math content of this blog, here's a related rates problem for you: if the radius of my head is growing at a constant rate of 50 meters per second, then at what rate is the volume of my head growing when its volume is 100 cubic meters?

If my head grows to 100 m^3, then you, the reader, won't have to worry about the wild success of this blog leading to advertising content; I'll just sell ad space on my forehead. Hm, that'll make stealth difficult on those urban caches... I should rethink this.

Seriously, I don't think I have anything special to offer here. I am no fountain of knowledge about geocaching. In fact, almost every geocacher I know has more cache finds than me. But if someone sees something here that leads to another social connection -- of which I've enjoyed many already -- then it will have served its purpose. It's a sort of virtual event cache.

Thanks also to zman for choosing not to broadcast the story I told at WeekNIGHT in Cottage Grove about my disturbing the natural environment of Lakeville in reckless pursuit of a cache. I guess he didn't want it construed as endorsement of a particular brand of chainsaw. Kidding, kidding... still, I don't want it to get around.

In other news... rickrich had to remove the Where's Yoda calculator from his webspace; his ISP identified it as malware. I think it's because the puzzle is based on the Pythagorean Theorem. Shady Pythagoreans...

pathtags.com has changed the status of my order from "unshipped" to "in progress". Could it be?! Maybe I'll have some tags to share in time for Breakfast Buddies in Richfield on Saturday... two FTFs in two days: knowschad's Little Crow and Millah's A or A ?... 25 caches on Sunday, most of them orange... in case you haven't noticed, Bobcam -- prolific Twin Cities cache hider and finder -- is 4th (down from 2nd; come on, Bobcam!) in the USA in Find Rate, according to INATN. Started at the end of September 2007, has >1000 finds... WeekNIGHT is at Ham Lake on Wednesday. I have new tires, so I might be able to make it.

Where's "Where's Yoda?"?

Blogger has disabled my page Where's Yoda? due to a violation of Terms of Service. I doubt that it's because there is a photo of a Yoda Pez dispenser that I did not take myself. Reading the discussion groups, I think that a bot has identified the script on that page as spam. Many people are finding it difficult to get responses out of Blogger, so I am not optimistic that it will be up and running anytime soon.

Anyone have suggestions on where to host this little calculator? I don't want to put it on my work web space, and I don't want to pay.

When our local cache reviewer asked me to move that calculator off this blog, because Groundspeak doesn't want cache pages linking to commercial sites, he was doing me a favor; otherwise, this blog would now be disabled. Who knows, maybe it will be soon, and I'll have no idea why and no way of finding out.

UPDATE: rickrich has generously offered to host the Where's Yoda? calculator. Blogger can take their sweet ol' time. And they will.

Time to take a deep breath.

After publishing Where's Yoda? last week and amusing myself and, I hope, others with alternate approaches to a solution, I turned my attention on Saturday to closing out the Plato's Five Gems series. I had the kids for the afternoon at Edinborough Park in Edina (and of course checked for nearby park'n'grabs, but the timing didn't work out), so I was free for a little while on Saturday evening to place Dodecahedron and Bunganator's Grand Slam.

I had previously released Octahedron, Icosahedron, Tetrahedron, and Cube, and so I returned to those caches to drop off clues for the Grand Slam. When I returned to my marked location for Dodecahedron, I was alarmed that the coordinates were a good bit off, but I hope that the geobeacon that the cache sits in will announce its presence enough to forgive some fluky coordinates. It's hard to juggle coordinate changes and the fact the puzzles are closely tied to the digits.

The Grand Slam cache was fun to place, because the cache itself is an icosahedral die. A very small number of cachers have the clues from all four of the old caches in the series (I'm emailing them to previous finders on request), so it could be a while until Grand Slam is found.

It was a little nerve-wracking Sunday and Monday, because I placed Dodecahedron too close to an unsubmitted cache that of course I was unaware of. But thanks to some mysterious and much appreciated dealings between our hard-working local cache reviewer and a gracious fellow cache hider, Dodecahedron was allowed to nestle in among its friends.

I must say, for the record, that I believe cache hiders should not be allowed to hold a location by reporting a cache but not submitting it. Priority should be given to the first to submit, not the first to report. That said, it has happened to me twice out of nine hides so far, and it has worked out for the best in both circumstances.

This is particularly bothersome for folks who hide mainly puzzle caches, because often the puzzles have to be reworked if the final location is changed.

Sunday Millah and I headed to Lakeville, mainly to finish off Bunganator's Climb On series of puzzle caches about rock climbing. We tried to pick off some traditionals in the area, too, and toward the end of the trip, we realized that we had around 25 finds and that I might be close to 300. Turns out, I was at 297 at the end of the day, so this morning I grabbed two on the way to Millah's puzzle cache Read 'Em And Weep, which came out of King Boreas' awesome Jukebox Hero seed cache.

Time to take a deep breath. Nine cache hides feels like plenty right now.