Posted 12 December 2012 - 10:08 PM

This is kind of like the same deal as trying to use pi as a hash table. Since you heard that pi contains any given sequence of digits *somewhere*, why not just find the offset of that sequence in pi and use that to refer to the sequence, and boom! Infinite compression. Well, no, not so fast - the offset is usually going to be larger than the sequence itself, a direct result of information theory.

Your problem is essentially trying to approximate an arbitrary triangular mesh with a smaller list of bounded parametric equations. This works fine for simple surfaces, as you've seen, such as spheres, cylinders, tori, boxes, or any combination of those (this includes the detail-less TIE fighter you mention). But in general, this problem is hard.

You could look at NURBS, which are implicit approximations for simple, well-behaved surfaces. The idea is that you choose control points along your desired surface, and interpolate smoothly between them using a form of B-splines. But for complex, irregular surfaces, such as a tree, they don't work very well as they require roughly as many control points as you'd need triangles. So it's not a general-purpose solution, but it works well in practice if you use them for the right surfaces.

In reality, any algorithm which solves your problem will be plagued by the same issue. For well-behaved meshes, it'll work well, but for all other meshes, I suspect it will either:

- produce an output roughly the same size as the input

- take exponential time

- both of those

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

- *Pessimal Algorithms and Simplexity Analysis*