Search This Blog

Friday, March 28, 2008

Exercise for the Reader Solved

Or rather, my conclusion about the answer to this question on the test (I posted the question to see if anyone else could figure it out) was confirmed by the teacher: there is no way to reduce the storage of any set of arbitrary points below the 96 bits required for the raw coordinates. There was an error in the question; specifically, the teacher forgot to mention one additional constraint about the values of the coordinates (though he hasn't said what it was, yet).

As for possible solutions. If it were known that all points were coplanar, you could store the normal of the plane and first point (or the first three points themselves), then convert all other points to 2D coordinates. You could use any manner of 2D coordinate system (they'll all use the same amount of space to store), but as we know the first three points are not collinear, I'd say the easiest would be barycentric coordinates. This was the first thing that came to mind while I was taking the test, but I asked and he said that I couldn't assume all points were coplanar.

Alternately, if you knew something about the locations of the points with regard to the plane, such as that they formed a regularly-spaced grid, or occurred periodically on a curve, you could reduce each point to a single value - the distance from the plane - with some overhead for describing the pattern the points appear on. Given that the hint the teacher gave me after I had finished the test was "height map", I'm guessing this is what he had in mind.

2 comments:

david said...

Isn't that how FLAC works, kind of? Finds a function close to the audio samples, then stores the distance from the function?

Olivier Ragain said...

hi,
My english must be really bad but wasn't the question regarding the set of n points ?
Your answer of 96 bits seems to be focused on the space that 1 points take. And so does not answer the question (kind of makes me wonder if I understood the question)

The second part of your news is much more like what i though the answer should be, but is that what you marked on your test or something else entirely ?