Approximate Isocontours and Spatial Summaries for Sensor Networks

We consider the problem of approximating a family of isocontours in a sensor field with a topologically-equivalent family of simple polygons. Our algorithm is simple and distributed, it gracefully adapts to any user-specified representation size k, and it delivers a worst-case guarantee for the quality of approximation. In particular, we prove that the topology-respecting Hausdorff error in our k-vertex approximation is within a small constant factor of the optimal error possible with Theta(k/log m) vertices, where m is the number of contours. Evaluation of the algorithm on real data suggests that the size increase factor in practice is a constant near 2.6, and shows no error increase. Our simulation results using a variety of synthetic and real data show that the algorithm smoothly handles complex isocontours, even for representation sizes as small as 32 or 48. Because isocontours are widely used to represent and communicate bi-variate signals, our technique is broadly applicable to in- network aggregation and summarization of spatial data in sensor networks.