World Line

The Knight Metric

with 3 comments

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 cellsx, yto 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)

whereM=\max{\left(|x|,|y|\right)} andm=\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

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 maked_K(A,B)=4and just y would maked_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.

Written by Adrian Petrescu

October 25, 2010 at 5:51 am

3 Responses

Subscribe to comments with RSS.

  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😦

    Adrian Petrescu

    October 26, 2010 at 10:34 pm

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


    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.

      Adrian Petrescu

      December 21, 2010 at 2:21 am

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: