L

まず原点 O と点 P, Q を含む最も粗い正方格子を求める問題を考えます。
P を原点に対して 90 度回転した点を P' とすると、

point gcd(point P, point Q){
if(dist(P, O) > dist(Q, O)) swap(P, Q);
if(P == O) return Q;
find integers n, m s.t. dist(P, Q+nP+mP') is minimal
return gcd(P, Q+nP+mP')
}

このような操作をすると原点からの距離が毎回 1/sqrt(2) 倍以下になるので log 回で終わります。
O と gcd(P, Q) を正方形の一辺とするような正方格子が最も粗い正方格子です。