TY - GEN

T1 - Covering arbitrary point patterns

AU - Mazumdar, Arya

AU - Wang, Ligong

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84875735743&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84875735743&partnerID=8YFLogxK

U2 - 10.1109/Allerton.2012.6483478

DO - 10.1109/Allerton.2012.6483478

M3 - Conference contribution

AN - SCOPUS:84875735743

SN - 9781467345385

T3 - 2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012

SP - 2075

EP - 2080

BT - 2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012

T2 - 2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012

Y2 - 1 October 2012 through 5 October 2012

ER -