一般には、実数上で定義された（二変数）区分線形関数が \((x_0,y_0)\) で最小値を取るとしても、定義域を整数に制限したときに最小値を取る \((m_0,n_0)\) が \((x_0,y_0)\) の十分近くにあるとは限りません。例えば、以下の関数を考えます。

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

\(g\) の実数引数の関数としての最小値は \(g(5, 0.5) = 0\) ですが、整数引数での最小値は \(g(0, 0) = g(10, 1) = 1\) で、\((5, 0.5)\) からは「離れて」います。（正確には、\(\max(|n_0-x_0|,|m_0-y_0|) = 5\) だけ離れています。）この様子は等高線プロットを見るとよくわかります。

すなわち、等高線が横に細長い多角形であるが故に、実数引数で最小値を取る点の周りの格子点を避けて、先に遠いところにある格子点に触れてしまうのです。

これが、\((x_0, y_0)\) を取り囲む \(4\) つの格子点 \((n_0, m_0)\) を見るだけでは正しい最小値を得ることができない理由です。それにもかかわらず、解説では探索範囲を \(1\) 広げるだけで十分だと主張しています。何故でしょうか？

これは、元の関数 \(f(x,y)\) の場合には多角形の辺が「変に」傾くことがないからです。実は、多角形のすべての辺は水平か、垂直か、斜め \(45^\circ\) となっています。これは、 \(f(x,y)\) の偏微分を計算するとわかります。（等高線は、常に勾配に垂直です。）

\(\max(|x|, |y|) = \max(x, y, -x, -y)\) を用いると、\(\max(|2Bx+e_1|,|2Ay+e_2|)\) の勾配は

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

のいずれかであり、\(\max(|2Ax+e_3|,|2By+e_4|)\) の勾配は

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

のいずれかです。したがって、 \(f(x,y)\) の勾配は

• \(\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}\)

のいずれか（復号はすべての組み合わせを取る）です。しかしよく見ると、この \(16\) 個のすべての場合において、勾配は \(x\) 成分しか持たないか、\(y\) 成分しか持たないか、\(x\) 成分と \(y\) 成分の絶対値が等しいことが分かります。これにより、等高線のなす多角形の辺の傾きは常に \(0,\infty,1,-1\) のいずれかであることが従います。

この条件のもとで \((x_0, y_0)\) を含む等高線の多角形を伸ばしたときに、\(\max(|n_0-x_0|,|m_0-y_0|) \ge 2\) に到達しながらそれより近い点に一切触れない、ということはできないことが示せます。実際、もし整数引数関数が \((m_0, n_0)\) で最小値を取るならば、（その点を下図の中央に描いたときに）それを含む等高線は以下の青い領域の中に入らなくてはなりません：

したがって、\(\max(|n_0-x_0|,|m_0-y_0|) \ge 2\) となることは不可能です。

上記の議論では、議論を簡単にするため \((m_0,n_0)\) の方を固定しましたが、\((x_0,y_0)\) を固定すると、候補点を更に絞り込むことができます。この候補点は、\((x_0,y_0)\) （緑の点）がセル内の \(4\) 領域のうちどこに属するかによって、以下のようになります：