Covering point patterns

A source generates a “point pattern” consisting of a finite number of points in an interval. Based on a binary description of the point pattern, a reconstructor must produce a “covering set” that is guaranteed to contain the pattern. We study the optimal trade-off (as the length of the interval tends to infinity) between the description length and the least average Lebesgue measure of the covering set. The trade-off is established for point patterns that are generated by a Poisson process. Such point patterns are shown to be the most difficult to describe. We also study a Wyner-Ziv version of this problem, where some of the points in the pattern are known to the reconstructor but not to the encoder. We show that this scenario is as good as when they are known to both encoder and reconstructor.