On the Minimal Teaching Sets of Two-Dimensional Threshold Functions
Max A. Alekseyev, Marina G. Basova, Nikolai Yu. Zolotykh · SIAM Journal on Discrete Mathematics · 2015
It is known that a minimal teaching set of any threshold function on the two-dimensional rectangular grid consists of 3 or 4 points. We derive exact formulae for the numbers of functions corresponding to these values and further refine them in the case of a minimal teaching set of size 3. We also prove that the average cardinality of the minimal teaching sets of threshold functions is asymptotically $ icefrac{7}{2}$. We further present corollaries of these results concerning some special arrangements of lines in the plane.