14
$\begingroup$

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...)

Improve this question
$\endgroup$
4
  • $\begingroup$ I admit that my intuition is that you should just get the normal Euclidean distance... It seems that for finer and finer chessboards, the L-shaped moves a night must make would disappear, and you would only see straight lines. $\endgroup$
    – Simon Rose
    Commented Sep 28, 2011 at 18:28
  • 1
    $\begingroup$ Ah, that can't be right. This construction is constnt for points on the original lattice Z^2, so what I said makes no sense. $\endgroup$
    – Simon Rose
    Commented Sep 28, 2011 at 18:30
  • $\begingroup$ Similarly, one could define a "king distance", which has unit ball the square with corners at $(\pm 1, \pm 1)$ and a "rook distance", which has unit ball the square with corners at $(\pm 1, 0), (0, \pm 1)$. (The "rook distance" is really the distance which corresponds to a piece which can move $(\pm 1, 0)$ or $(0, \pm 1)$ on each move.) Somewhat surprisingly, the "bishop distance" defined in this way is the same as the king (or queen) distance... $\endgroup$
    – Michael Lugo
    Commented Sep 29, 2011 at 0:21
  • 7
    $\begingroup$ Here's an exact formula for the Knight distance $d$ from $(0,0)$ to $(x,y)$. By symmetry we may assume $0\leq x\leq y$. Clearly $d$ satisfies $2d\geq y$, $3d\geq x+y$, and $d\equiv x+y\bmod2$. Then $d$ is the smallest integer satisfying these conditions, unless $(x,y)=(0,1)$ or $(2,2)$ when the distance is $3$ or $4$ respectively, exceeding the expected answer by $2$. These exceptions are well-known to chessplayers... On a finite chessboard the edges produce one more exception: the distance from a corner to its diagonal neighbor is $4$, not $2$ (the knight would have to leave the board). $\endgroup$
    – Noam D. Elkies
    Commented Sep 29, 2011 at 3:56

1 Answer 1

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ One can define a generalized taxicab metric for every symmetric convex polygon. $\endgroup$
    – Will Sawin
    Commented Sep 28, 2011 at 20:45
  • $\begingroup$ Thanks. So, it seems the catchword is "taxicab metric". I was not aware that a concept analogous to "knight distance" had (more or less) already been addressed in history. $\endgroup$
    – Qfwfq
    Commented Sep 29, 2011 at 1:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .