Covering Point Patterns

Abstract

An encoder observes a point pattern---a finite number of points in the interval $[0,T]$---which is to be described to a reconstructor using bits. Based on these bits, the reconstructor wishes to select a subset of $[0,T]$ that contains all the points in the pattern. It is shown that, if the point pattern is produced by a homogeneous Poisson process of intensity $λ$, and if the reconstructor is restricted to select a subset of average Lebesgue measure not exceeding $DT$, then, as $T$ tends to infinity, the minimum number of bits per second needed by the encoder is $-λ\log D$. It is also shown that, as $T$ tends to infinity, any point pattern on $[0,T]$ containing no more than $λT$ points can be successfully described using $-λ\log D$ bits per second in this sense. Finally, a Wyner-Ziv version of this problem is considered where some of the points in the pattern are known to the reconstructor.

5 pages. Submitted to ISIT 2011