Covering arbitrary point patterns

This paper considers the problem of covering an arbitrary point pattern - a set of λT points in the interval [0, T] - with a subset of [0, T] that is drawn from a predefined codebook. The subset is required to contain either all or a certain proportion of the points in the pattern, depending on the problem setting. Also, all subsets in this codebook must have Lebesgue measure not exceeding dT where d ≤ 1 is a given constant. The problem of interest here is to find the trade-off between d and the size of the codebook. We find this trade-off asymptotically as T goes to infinity. When the subset is required to cover all the points, the answer turns out to be the same as in the case where the points were randomly generated by a Poisson process of intensity λ, the latter being obtained in an earlier work.