World Line

The Knight Metric

Here’s a problem I’ve been thinking about. I’m curious if anybody has any ideas about it; I have reasons to believe it might be very hard (in the theoretical sense) but I haven’t given it much time yet.

Consider a (possibly infinite) two-dimensional integer grid $G\subseteq \mathbb Z^2$, with some finite subset of its cells colored black. We consider two cells$x, y$to be connected if $||x - y|| = \sqrt{5}$; that is, if the cells are a knight’s move apart. Write a function that computes the least number of additional cells that would need to be colored black in order to ensure that there exists a connected path between any two black cells.

The trickiness comes from the fact that adding a black square can either increase or decrease the total number (it’s not hard to come up with examples of either possibility), so the problem resists simplification. I have no idea if this can be computed in polynomial time or space. I thought of it in the context of geometric constructions, for which computability results are notoriously difficult, but it smells like this can be solved in purely graph-theoretic terms. There is actually a closed formula for the “knight’s distance” between two points, though it is a bit complicated:

$d_K(x,y) = \max{\left(\lceil\frac{M}{2}\rceil, \lceil\frac{M+m}{3}\rceil\right)} + (M+m) - \left(\max{\left(\lceil\frac{M}{2}\rceil, \lceil\frac{M+m}{3}\rceil\right)}\pmod{2}\right)$

where$M=\max{\left(|x|,|y|\right)}$ and$m=\min{\left(|x|, |y|\right)}$. If we take each pair of given black squares, calculate their shortest distance, we can use that as an admissible heuristic to an A* search to find the shortest paths in polynomial time. Easy.

Except that it doesn’t work. It’s minimizing the wrong thing: distance, instead of the minimum number of squares. Consider the following configuration:

Figure A

It’s easy to see that there’s (two) ways to solve this problem by adding just a single square (either x or y). Therefore, the answer to our problem is 1. However, the above approach would instead notice that it could make all the distances be less than or equal to 2 by adding x and y and z, while adding just x would make$d_K(A,B)=4$and just y would make$d_K(A,D)=4$.

Thus the problem has some non-local properties that I don’t really know how to translate into graph-theoretic terms, unless I just consider all paths within a certain ball whose size is linear in the diameter of the graph, but that would be exponential.

If anyone has any clever ideas, I’d be interested in hearing about it.

October 25, 2010 at 5:51 am

3 Responses

1. William pointed out this is no different from the regular minimally connected component problem, for which the straightforward dynamic programming approach works just fine. I don’t know why I originally rejected this, but he convinced me. Oops 😦

October 26, 2010 at 10:34 pm

2. Isn’t the problem similar to Steiner Tree Problem?

http://en.wikipedia.org/wiki/Steiner_tree_problem

mashuq

December 21, 2010 at 2:10 am

• Yeah, it’s like a discrete version of that, which makes it much simpler. William described a solution to me with a runtime roughly proportional to the area of the circle circumscribing all the given black squares.