Asymptotics of the number of threshold functions on a two-dimensional rectangular grid (Q1759858)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Asymptotics of the number of threshold functions on a two-dimensional rectangular grid |
scientific article |
Statements
Asymptotics of the number of threshold functions on a two-dimensional rectangular grid (English)
0 references
22 November 2012
0 references
For a rectangular grid \(G=G(m,n)=\{0,\dots,m-1\}\times\{0,\dots,n-1\}\), where \(m,n\geq 2\), a function \(\tau:G\to\{0,1\}\) is called a (two-dimensional) threshold function if there exists a line separating the sets \(\tau^{-1}\left(\{0\}\right)\), \(\tau^{-1}\left(\{1\}\right)\). This paper is concerned with improved asymptotic estimates for the number \(\tau(m,n)\) of threshold functions when \(2\leq m\leq n\); and for the special case \(\tau(n,n)\), denoted by \(\tau(n)\). When \(m\leq n\), bounds for \(t(m,n)\) in [\textit{D. M. Acketa} and \textit{J. D. Žunić}, Inf. Process. Lett. 38, No. 3, 163--168 (1991; Zbl 0737.68080); \textit{M. A. Alekseyev}, SIAM J. Discrete Math. 24, No. 4, 1617--1631 (2010; Zbl 1231.94092)] are improved to \(t(m,n)=\frac{6}{\pi^3}(mn)^2+O\left(mn^2\right)\) as \(m\to\infty\). A bound of [\textit{J. Koplowitz} et al., IEEE Trans. Inf. Theory 36, No. 1, 192--197 (1990; Zbl 0709.68077)] is improved to \(\tau(n)=\frac{6}{\pi^2}n^4+O\left(n^3\right)\) as \(n\to\infty\).
0 references
threshold function
0 references
rectangular grid
0 references
integer lattice
0 references
asymptotic formulas
0 references