To appear
Previous: 8 Compressing ETOPO5
Altho regularly gridded data compresses quite well,
how might we compress a TIN file? There are the 
coordinates of the points, and the six neighbors (on average) of
each point.
Let the number of points in the original DEM be N, typically,
. Let K be the number of points selected to be
in the TIN. If the TIN is to be worth using, then 
. The
easiest way to store the points is to list their coordinates in
the original DEM, at a cost for each 
) of 
bits/point. However, the smaller information-theoretical space
comes from the number of subsets of K points selected from N,
and is
bits per point, where 
counts binomial
combinations, e.g., 
. If,
say, K=65,535, then this is a significant reduction from 20.5 to
4.5 bits per point.
Compressing heights is hard since the irregular topology makes run-length encoding difficult, tho not necessarily impossible. Compressing the topology is harder. If there is nothing stored inside each triangle, then they might be constructed as needed from the point adjacencies.
The average point has six neighbors, and the simplest implementation is an array of the ID numbers of the neighbors. 16 bits per ID, plus a count, gives about 100 bits per point. This is by far the dominant storage cost. Note that the storage cost for a hierarchical structure will be even larger. There are more compact methods of storing a planar graph, so that each edge requires only a few bits. The compact format has to be expanded before the graph can be traversed, but that's already the case with the points. To understand the compact planar graph structure, consider how to store a binary tree compactly.
With the simple binary tree format, each node contains two
pointers, for its two sons. We can traverse and update this
structure, but it costs 32 bits per node (if there are under
nodes). We might instead store only the information
about whether or not each node has a left son, and whether it has
a right son, in 2 bits total per node. We traverse the tree in
some well-defined recursive order, such as the node, then its left
subtree, and finally its right subtree, listing the 2 bits for
each node in sequence. Following that, we can list in sequence
any internal information about each node.
We can extend this to a planar graph, though the structure is more
complicated; see Jacobson[17,16], Kannan et
al[18], and Turan[34]. An unlabeled
triangulation can be stored in 
bits per node;
the K labels require another 
. The graph would probably
need to be expanded before being used.
Altho the TIN initially does not seem competitive with the regular grid compression methods described earlier, with these succinct codings, it might be. Which is actually better remains an open question.
To appear
Previous: 8 Compressing ETOPO5