
Originally Posted by
nburns
A lot of savings will likely come from putting the coordinates in a more favorable order to narrow their ranges. For instance, if you want to send a set of integers where order doesn't matter, the first thing to do is sort them; then you can send just the smaller deltas. Potentially even better than simple sorting is deliberately sending them out-of-order so the ranges are bounded on both ends: if you have to send 3 positive integers x1<=x2<=x3, you could send x3 first, which provides a maximum for the remaining two. You can put all the integers on a tree and exploit bounded ranges recursively. You can do this in a predetermined order, e.g. just repeatedly cut the set in half like a perfectly-balanced binary tree. Or, potentially more interesting, you could search for an optimal shape for the tree.
In the case of polygons, there is an algorithm in CLR for optimal polygon triangularization using dynamic programming -- this finds a triagularization, which is equivalent to putting the vertices on a binary tree. It would be interesting to see what could be done with an appropriate cost function and encoding.