Maximal pattern complexity, dual system and pattern recognition

For a family Ω of sets in R2 and a finite subset S of R2, let pΩ(S) be the number of distinct sets of the form S∩ω for all ω∈Ω. The maximum pattern complexity pΩ*(k) is the maximum of pΩ(S) among S with S=k. The S attaining the maximum is considered as the most effective sampling to distinguish the sets in Ω. We obtain the exact values or at least the order of pΩ*(k) in k for various classes Ω. We also discuss the dual problem in the case that Ω=∞, that is, consider the partition of R2 generated by a finite family T⊂Ω. The number of elements in the partition is written as pR2(T) and pR2*(k) is the maximum of pR2(T) among T with T=k. Here, pΩ*(k)=pR2*(k) does not hold in general. For the general setting that Ω is an infinite subset of AΣ, where A is a finite alphabet, Σ is an arbitrary infinite set, and pΩ*(k)=maxS= kΩ|S, it is known that the entropy h(Ω):= limk→∞logpΩ*(k)k exists and takes value in log1,log2,...,logA. In this paper, we prove that the entropy h(Σ) of the dual system coincides with h(Ω).