Saturday, May 24, 2008

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?

1 comment:

Starhawk Laughingsun said...

Well i stumbled across this doing research on a fractal program I am writing. It is not a 3-d landscape generation program but I can shed some light on your questions. Algorithms to generation fractal mountains and islands and so on are relatively simple and a google search would find all kinds of examples and code and so on. As to the Hausdorff dimesnion, yes fractals of this sort do have fractional dimensions and so probably there is some justification to the use of the term "2 and 1/2" dimensions by the 3-d graphics artist you mention. However the exact dimension of any particular landscape looking fractal is unlikely to be 2 and 1/2 exactly and would need to be calculated or approximated for that particular image to get a real value for its dimension.