What is the limit of the "knight" distance on finer and finer chessboards?

2011-09-28T18:18:50Z

Consider the "infinite chessboard" on the plane. Think of it as the lattice $X_1:=\mathbb{Z}^2$, and also finer chessboards $X_n$ corresponding to $\frac{1}{n}\cdot \mathbb{Z}^2$, $n\geq 1$. Given two squares (i.e. vertices) $u,v$ of $X_n$ one can define the "knight distance" $d_n(u,v)$ as the minimum number of moves that a "knight" (moving as in the usual game of chess) must do to get from $u$ to $v$, divided by $n$.

Now take two points $a,b$ on the plane $\mathbb{R}^2$, and define their "knight distance at step $n$" to be the minimum of $d_n(u,v)$ for $u,v\in X_n$ such that $d_E(u,a)$ and $d_E(v,b)$ are minimal (where $d_E$ is the Euclidean distance on $\mathbb{R}^2$).

Define the "knight distance" on the plane by $d_K(a,b):=\lim_{n\to\infty}d_n(a,b)$.

Does it define an actual distance (metric) on $\mathbb{R}^2$? Assuming it does, how does the spheres look like for this metric? Any interesting properties? Is there a self-homeomorphism of $\mathbb{R}^2$ that pullbacks $d_K$ to $d_E$?

(This was a question I happened to ask myself at high school -and never thought really to answer- of which I was reminded of by just reading this MO thread by Joseph O'Rourke. Provided it makes sense, it still looks like a legitimate question to me...)

Answer by Will Sawin for What is the limit of the "knight" distance on finer and finer chessboards?

2011-09-28T18:59:22Z

Let $(x,y)$ and $(x+2a,y+a)$ be points in space. Then clearly the distance between these two points is $a$. Therefore, the unit ball around 0 must contain the octagon with vertices $(2,1)$, $(1,2)$, $(-1,2)$ and so on.

I argue that this is all it contains. To see this, construct linear invariants showing how far you can get with $k$ knight's moves of length $1/k$. For instance, each knight's move increases $x$ by no more than $2/k$, so if $|x_1-x_2|>2$ then $d(x_1,x_2)>1$. Similarly, it increases $x+y$ by no more than 3. With the 6 other linear functionals, one can restrict the unit ball to that octagon.

This metric is a kind of taxicab metric. It is not like the Euclidean metric because there are an infinite number of geodesics of length 1 between $(0,0)$ and $(2,0)$.

So, answers: Yes, octagons, I can't think of any other than the properties of the taxicab metric, no.

What is the limit of the "knight" distance on finer and finer chessboards? - MathOverflow

What is the limit of the "knight" distance on finer and finer chessboards?

Answer by Will Sawin for What is the limit of the "knight" distance on finer and finer chessboards?