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?

GSAK: Getting to know you, getting to know all about you...

foundinthewild sent me some helpful hints about using Garmin's POI Loader to add custom icons and custom points of interest to the microSD card of the 60CSx. [Edit: Here they are:]

I am attaching a zip file of the modified versions of the gsak macros and my icon set. I have some duplicate icons, but the important ones, found, not found, multi, puzzle, virtual, disabled, and final locations are there. I made some mods to the macro code, like drop2, mark the found caches with * (when I choose to include them), and use the difficulty/terrain rating system of 1,A,2,B,3,C,4,D,5. You can find the mods by searching [for my initials] since I comment the code. I also increased my smartnames in gsak by 2 characters to give me a better sense of the cache names.

It takes a few minutes to run on my older machine for about 6800 caches for the state of MN. It will use around 1.2 MB on the memory card i.e. not very much.

----------------------
One time:
The original / latest gsak macro (untouched by me) can be found at: http://gsak.net/board/index.php?showtopic=3172. My version is attached to this email.

Download and install of the poiloader from Garmin:
http://www8.garmin.com/products/poiloader/

Set up your POI folder and unzip the CustomPoiIcons zip or from my poi_files.zip file . My version is attached.

Go to your cache database, choose Macro /Run/Manage and install the macro GarminCsvPoiExport.gsk if it's not already installed. This file is in the poi_files.zip file, too.
-------------------
File update and replacement:

Set the GPS to USB connected drive. (Menu, menu, setup, interface, USB). Using windows explorer, find k:\garmin\poi (k: is your usb mapped drive). The folder will start out blank or with a file called "poi.gpi" but you can put more than one file there.

After the gsak macro is done running on your database, run POI loader program from windows, finding the usb connected drive. I choose not to use proximity alerts in the options. You run through each type of file it finds in your POI folder or use express. When it is done, check your folder with windows explorer and you should see a file called 'poi.gpi'. I RENAME that file to something like 'minn080131.gpi' which means you can rerun the export macro on a different database, load the next gpi file as poi.gpi, rename it, say "Florida.gpi" or something, and repeat for many databases. It needs the .gpi extension.

Remember to "Safely Remove" your hardware, and the gpsr restarts in standard mode. Find / 'Custom Points of Interest' defaults to closest but you can search by smartname or the drop2. Once you find a cache, use find/find/select waypoint and "save" the waypoint as a geocache. This should place it in the calendar if needed for later review.

The symbols show up when you are zoomed in to about 0.8 miles or closer. This is supposed to help with the clutter. I set up my garmin map from the map display: menu/setup map/map points/ max zoom at 0.8mi.

I have an intermittent micro SD card, so I always verify a good poi load before heading out and re-running poiloader usually fixes it.

I have used several different poi folders for unique locations. I just copy all of the icons from the main poi files folder to the new one.

Let me know how this works for you.


Haven't tackled that project yet, though I did download the loader and check that I could browse around the card as a USB mass storage unit. It appears that the maps take up about 1GB and change, so I'm assuming that's a 2GB card I've got in there and so there's room to add some POIs.

I set up a dedicated email account to collect pocket query emails from Groundspeak so that GSAK can process them automatically.

Then I changed how GSAK writes the waypoint description to the GPSr. Now I'm using

%Smart/%By=4/%typ1/%con1/%dif1a/%ter1a

which gives a shortened version of the cache name, the first four letters of the name of the hider, and one-letter codes for the cache type, container, difficulty, and terrain.

I am reluctant to start using custom icons and custom points of interest, because my favorite feature of the 60CSx is the Geocaching Mode, in which you can press a Found button so that the cache is saved to your calendar for easy logging later. Would be interested to hear your workarounds on this if you do use a bunch of custom POIs. [Update: foundinthewild tells me that when he finds a cache that is not a traditional, he changes the icon and find it again in order to save it to the calendar. Good enough for me. I'm on it!]

---

Time to change Plato's Five Gems: Dodecahedron to a large container! See this post on Boing Boing.

When I take my old laptop to the hospital to recover some lost data, I'll try to retrieve a photograph of the huge icosahedron I made with some ninth graders during a summer math camp a few years back. It was about fifteen feet high, and it was made out of 10-foot lengths of 2x2 lumber and these special Starplate connector joints.

[Shameless commerce division: Anyone want these at a discount? I'm still dragging them around from basement to basement.]
Reaction was mixed. My mathematical colleagues said "Spectacular!" My administrative colleagues were not happy. Something about giving ninth graders power tools without their parents' permission...

Let me tell you something though: those kids couldn't help but leave camp knowing V - E + F = 2!

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.

The backdoor to Where's Yoda?

One thing I love about geocaching is that each person can interact with the game/sport/hobby however he or she chooses. If you pull out a laptop at a pick-up soccer game, you will get looks.

Yesterday, I published a puzzle cache called Where's Yoda?. In order to solve the puzzle, the cacher uses a Javascript calculator that I hacked together from some code I stole from a colleague. That calculator is now here and not on this blog because GC.com does not like it when cache pages re-direct to pages that have links to commercial sites, as I do here (for convenience, not necessarily to promote those products).

I am fascinated with ways that cachers can get around actually solving a puzzle. One way would be to look at the code in the page source for the calculator, so I had to figure out how to encrypt that code. (And if you can decrypt that, then more power to you!)

Another way that cachers get around solving puzzles is by flooding geochecker.com with checks until they hit Success! This Yoda puzzle has 10^6 possible answers, so that's not really a problem here.

A third way is by plotting possible answers on Google Earth. For example, on Millah's musical puzzle cache Final Countdown I didn't have the hundredths of west or the thousandths of north, so I plotted a rectangle in Google Earth and guessed where it should be (incorrectly, it turns out).

In order to discourage this, once the cacher finds the coordinates of Yoda (X,Y), I give the cache coordinates as (7X-2Y+230,Y^2-7X^2-48339), so that distances in Yoda-land don't correspond to distances in cache-land. (I realize that a box of 1'N by 1'W is not a square, but that can be accounted for.)

Well, around the time last night that the cache was published and the first responders were going after it, I realized that these formulas give a bit of a "back door" around the calculator (which gives the distance between a guess and Yoda's location). Here's how it goes:

7X-2Y+230 and Y^2-7X^2-48339 need to be between 0 and 999. If you use a computing package like Mathematica (which I'm using a lot these days for my multi-variable calculus course), then you can determine that there are only 339 (out of 10^6 !!!) possible locations for Yoda and hence the cache. Here's my code:

z = 0; For[x = 0, x < 1000, x++,
For[y = 0, y < 1000, y++,
If[-1 < 7 x - 2 y + 230 &&
7 x - 2 y + 230 < 1000 && -1 < y^2 - 7 x^2 - 48339 &&
y^2 - 7 x^2 - 48339 < 1000, z++;
Print[z, ": Yoda=", {x, y},
"--> cache=", {7 x - 2 y + 230, y^2 - 7 x^2 - 48339}]]]]

And here's some of the output:

1: Yoda={36,240}--> cache={2,189}
2: Yoda={36,241}--> cache={0,670}
...
339: Yoda={367,996}--> cache={807,854}

I'd like to figure out how to write a script that exports these coordinates to a KML or GPX file that Google Earth can then plot. I wonder how many of those 339 possible locations correspond to plausible hiding spots? Of course, this is all much more involved than just working with the calculator as intended.

Like I say, geocaching is whatever it means to you. And today, geocaching looks a lot like my job! Time to go grab some LPCs!

Why are there only five Platonic solids?

A Platonic solid is a convex polyhedron that has faces that are regular polygons and has the same number of regular polygons around each vertex.

See my series of (four, so far) caches related to Platonic solids: Plato's Five Gems: Tetrahedron, Cube, Octahedron, and Icosahedron. Dodecahedron coming soon!

Let's show that any Platonic solid has to be either a tetrahedron, a cube, an octahedron, a dodecahedron, or an icosahedron.

Let V, E, and F be the number of vertices, edges, and faces of the Platonic solid. Let N be the number of edges of each face, and let M be the number of faces (and hence also edges) around each vertex.

Then we have M x V = 2E and N x F = 2E (in each equation, we're noting that each edge has been counted twice).

Now we have to use Euler's formula: for a convex polyhedron, V - E + F = 2. I'll prove that later on. Substituting V = 2E/M and F = 2E/N, we get

2E/M - E + 2E/N = 2.

Divide both sides by 2E, and we get 1/M - 1/2 + 1/N = 1/E, or 1/M + 1/N = 1/E + 1/2.

Since E is positive, we must have 1/M + 1/N > 1/2, and also M and N have to be at least 3 (do you see why?). The only pairs (M,N) that satisfy these inequalities are (3,3) (tetrahedron), (3,4) (cube), (4,3) (octahedron), (3,5) (dodecahedron), and (5,3) (icosahedron). End of proof.

Now, why is Euler's formula true? There are lots of proofs, but here is one of the easier ones to understand:

Remove one face from your Platonic solid, thinking of it as just the outer skin of vertices, edges, and faces, not the stuff inside. If we can show V - E + F = 1 for that thing, then we will have shown that V - E + F = 2 for the polyhedron.

Imagine flattening that ball with a hole onto a table. That doesn't change V - E + F. Now, one at a time, remove an edge that is on the border and also remove the face that it is next to. E goes down 1, and so does F, so that's a net change of 0 to V - E + F. Continue doing that until you have one polygon left. That polygon satisfies V - E + F = 1, and so the original polyhedron satisfies V - E + F = 2. That proves Euler's formula.