We study the discrepancy of the following communication problem. Alice receives a halfplane, and Bob receives a point in the plane, and their goal is to determine whether Bob's point belongs to Alice's halfplane. This communication task corresponds to determining whether $x_1y_1+y_2\geq x_2$, where the first player knows $(x_1,x_2)$ and the second player knows $(y_1,y_2)$.

Denoting $n=m^3$, we show that when the inputs are chosen from $[m] \times [m^2]$, the communication discrepancy of the above problem is $O(n^{-1/6} \log^{3/2}n)$.

On the other hand, through the connections to the notion of hereditary discrepancy by Matou\v{s}ek, Nikolov, and Tawler (IMRN 2020) and a classical result of Matou\v{s}ek (Discrete Comput. Geom. 1995), we show that the communication discrepancy of every set of $n$ points and $n$ halfplanes is at least $\Omega(n^{-1/4} \log^{-1} n)$.

New parts in connection with discrepancy theory, and revised title.

We study the randomized communication complexity of the following problem. Alice receives the integer coordinates of a point in the plane, and Bob receives the integer parameters of a half-plane, and their goal is to determine whether Alice's point belongs to Bob's half-plane.

This communication task corresponds to determining whether $x_1y_1+y_2\geq x_2$, where the first player knows $(x_1,x_2) \in [n]^2$ and the second player knows $(y_1,y_2) \in [n]^2$. We prove that its randomized communication complexity is $\Omega(\log n)$.

Our lower bound extends a recent result of Hatami, Hosseini, and Lovett (CCC '20 and ToC '22) regarding the largest possible gap between sign-rank and randomized communication complexity.