Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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. –  Simon Rose Sep 28 '11 at 18:28
1  
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. –  Simon Rose Sep 28 '11 at 18:30
    
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... –  Michael Lugo Sep 29 '11 at 0:21
4  
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). –  Noam D. Elkies Sep 29 '11 at 3:56
add comment

1 Answer 1

up vote 10 down vote accepted

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.

share|improve this answer
    
One can define a generalized taxicab metric for every symmetric convex polygon. –  Will Sawin Sep 28 '11 at 20:45
    
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. –  Qfwfq Sep 29 '11 at 1:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.