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 tradeoff (as the length of the interval tends to infinity) between the description length and the least average Lebesgue measure of the covering set. The tradeoff is established for point patterns that are generated by homogeneous and inhomogeneous Poisson processes. The homogeneous Poisson process is shown to be the most difficult to describe among all point patterns. We also study a Wyner-Ziv version of this problem, where some of the points in the pattern are revealed to the reconstructor but not to the encoder. We show that this scenario is as good as when they are revealed to both encoder and reconstructor. A connection between this problem and the queueing distortion is established via feedforward. Finally, we establish the aforementioned tradeoff when the covering set is allowed to miss some of the points in the pattern at a certain cost.