In general, when a (two-dimensional) piecewise linear function defined on real numbers attains the minimum at \((x_0,y_0)\), the minimum value when the domain is restricted to integers is not necessarily attained at \((m_0,n_0)\) near enough. For example, consider the following function:

\[g(x,y) = 100 |10y - x| + |2y - 1|\]

As a real-valued function, its minimum is at \(g(5, 0.5) = 0\). However, as an integer-valued function, it takes the minimum at \(g(0, 0) = g(10, 1) = 1\), which is “far away” from \((5, 0.5)\). (Formally, we have \(\max(|n_0-x_0|,|m_0-y_0|) = 5\) for this case.) This can be visually understood by considering the contour polygons:

As you can see, the contour lines avoid the lattice points around the real-valued minimum point, and the first contour polygon that touches a lattice point is a tilted, horizontally long polygon.

This is why you cannot naively inspect the four lattice points \((n_0, m_0)\) surrounding \((x_0, y_0)\) to obtain the correct answer. Nevertheless, the editorial claims that it is sufficient to extend the search range only by one. Why is it valid?

This is because in our function \(f(x,y)\), the edge of a contour polygon is never “badly tilted”; instead, every edge is horizontal, vertical, or (anti-)diagonal. This can be verified by finding the partial derivative of \(f(x,y)\). Note that a contour line is always perpendicular to the gradient.

Using the identity \(\max(|x|, |y|) = \max(x, y, -x, -y)\) the gradient of \(\max(|2Bx+e_1|,|2Ay+e_2|)\) is one of

• \(\begin{pmatrix} \displaystyle \pm 2B \\ 0 \end{pmatrix}\)
• \(\begin{pmatrix} \displaystyle 0 \\ \pm 2A \end{pmatrix}\),

and the gradient of \(\max(|2Ax+e_3|,|2By+e_4|)\) is one of

• \(\begin{pmatrix} \displaystyle \pm 2A \\ 0 \end{pmatrix}\)
• \(\begin{pmatrix} \displaystyle 0 \\ \pm 2B \end{pmatrix}\).

Therefore, the gradient of \(f(x,y)\) is the sum of any of the two:

• \(\begin{pmatrix} \displaystyle \pm 2A \pm 2B \\ 0 \end{pmatrix}\)
• \(\begin{pmatrix} \displaystyle \pm 2B \\ \pm 2B \end{pmatrix}\)
• \(\begin{pmatrix} \displaystyle \pm 2A \\ \pm 2A \end{pmatrix}\)
• \(\begin{pmatrix} \displaystyle 0 \\ \pm 2A \pm 2B \end{pmatrix}\),

where the plus-minus sign can take any combination. But in any of the \(16\) cases, the gradient only has \(x\) component, only has \(y\) component, or the absolute values of \(x\) and \(y\) components are equal. This leads to the claim in the original editorial that the slope is either \(0,\infty,1\), or \(-1\).

Under this condition, a contour polygon that contains the real minimum \((x_0, y_0)\) can never stretch far enough to touch a distant lattice point where \(\max(|n_0-x_0|,|m_0-y_0|) \ge 2\) without also enclosing at least one lattice point strictly closer to \((x_0, y_0)\). Specifically, if a distant point \((m_0, n_0)\) attains the minimum of the integer-valued function (drawn at the center of the figure below), the shape of the contour polygon must fit inside the blue region:

Therefore, it cannot happen that \(\max(|n_0-x_0|,|m_0-y_0|) \ge 2\).

In the discussion above, we fixed \((m_0,n_0)\) for the sake of simple discussion; if we fix \((x_0,y_0)\) instead, which is illustrated as a green point, we actually obtain fewer candidates, relative to which of the four regions in a cell the point \((x_0,y_0)\) belongs to: