A characterization of 2-threshold functions via pairs of prime segments

Elena Zamaraeva, Jovisa Zunic

Published 2020-07-08Version 1

In this paper we study 2-threshold functions over a two-dimensional rectangular grid also known as intersections of two halfplanes. We provide a characterization for 2-threshold functions by pairs of oriented prime segments with certain properties, which we call proper. To this end, we first show that any proper $2$-threshold function $f$ can be defined by a proper pair of segments. Then we prove that such a representation is unique if $f$ has a true point on the boundary of the grid. Finally, we establish a bijection between almost all proper pairs of segments and almost all $2$-threshold functions. Due to this bijection almost all $2$-threshold functions admit encoding by ordered sets of 4 integer points.