Covering Point Patterns

DOI10.1109/TIT.2015.2453946MaRDI QIDQ2977256zbMATH OpenOpenAlexFDO

Authors Amos Lapidoth, Andreas Malär, Ligong Wang

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.3080

Mathematics Subject Classification ID

Information theory (general) (94A15) Coding theorems (Shannon theory) (94A24) Source coding (94A29) Rate-distortion theory in information and communication theory (94A34)

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 $lambda$, 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 $-lambdalogD$. It is also shown that, as $T$ tends to infinity, any point pattern on $[0,T]$ containing no more than $lambdaT$ points can be successfully described using $-lambdalogD$ 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.

Cited in

(1)

• Selecting Heavily Covered Points

This page was built for publication: Covering Point Patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977256)