What is the limit of the "knight" distance on finer and finer chessboards? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T03:29:44Z http://mathoverflow.net/feeds/question/76670 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76670/what-is-the-limit-of-the-knight-distance-on-finer-and-finer-chessboards What is the limit of the "knight" distance on finer and finer chessboards? Qfwfq 2011-09-28T18:18:50Z 2011-09-29T01:11:38Z <p>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$.</p> <p>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$).</p> <p>Define the "knight distance" on the plane by $d_K(a,b):=\lim_{n\to\infty}d_n(a,b)$.</p> <blockquote> <p>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$?</p> </blockquote> <p>(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 <a href="http://mathoverflow.net/questions/76623/growing-random-trees-on-a-lattice-rightarrow-voronoi-diagrams" rel="nofollow">thread</a> by Joseph O'Rourke. Provided it makes sense, it still looks like a legitimate question to me...)</p> http://mathoverflow.net/questions/76670/what-is-the-limit-of-the-knight-distance-on-finer-and-finer-chessboards/76673#76673 Answer by Will Sawin for What is the limit of the "knight" distance on finer and finer chessboards? Will Sawin 2011-09-28T18:59:22Z 2011-09-28T18:59:22Z <p>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.</p> <p>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.</p> <p>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)$.</p> <p>So, answers: Yes, octagons, I can't think of any other than the properties of the taxicab metric, no.</p>