1
$\begingroup$

I have a 2D grid of infinite size that can either be 4-connected or 8-connected (as defined in https://en.wikipedia.org/wiki/Pixel_connectivity). I am implementing breadth-first search on this grid starting at a particular node. I search up to and including the nodes at depth $D$ with $D \geq 1$. The nodes at depth $D+1$ are not added to the open set so that the search terminates at the completion of depth D. Also, some of the nodes can have obstacles so that I can't explore them. An example of the state upon starting to look at the nodes in a particular depth is shown below for 8-connected grids for $D = 3$.

. = accessible cell (not processed yet)
o = obstacle
- = accessible cell (in closed set)
+ = accessible cell (in open set)

Depth 1:
.........
.......o.
..o..o...
....+o...
.........
..o......
.......o.

Depth 2:
.........
.......o.
..o++o...
...+-o...
...+++...
..o......
.......o.

Depth 3:
.........
..++++.o.
..o--o...
..+--o+..
..+---+..
..o++++..
.......o.

Finished:
.........
..----.o.
..o--o...
..---o-..
..-----..
..o----..
.......o.

I would like to know if there is an upper bound on the largest size of the open set during the execution of the algorithm that is lower than $(2D-1)^2$ for 8-connected grids and $2D(D-1)+1$ for 4-connected grids (if my math is right, this is the number of cells that are of distance $D-1$ or less from a starting point under those connectivities, or the maximum number of points you can reach). I considered using the number of cells exactly at distance $D-1$ from the starting point as a tighter upper bound (if my math is right, then this is $max(8(D-1),1)$ for 8-connected grids, and $max(4(D-1),1)$ for 4-connected grids), but I realized that this could possibly underestimate the true number of cells because if there are obstacles, they might cause us to search cells at depth $D$ whose direct Manhattan/Chebyshev distance is less than $D-1$ away because we have to take a roundabout route to get to them. So it might be possible that we might end up with more than that many nodes in the open set.

Is it possible to come up with a tighter upper bound, preferably one that scales linearly with $D$ rather than quadratically if it exists? Knowing a better upper bound would allow me to allocate memory up front for the BFS queue, while not wasting too much memory on space that will never be used.

Edit:

After thinking about the problem for a bit, I realized that, for 8-connected grids, if you make a triangle with a winding path above the starting point, you can generate additional points in the open set without removing any of the points on the perimeter. Thus, unfortunately, the tighter upper bound I proposed above isn't true, at least for 8-connected grids. I'm not sure if a similar structure exists for 4-connected grids. I made an example, with the pixels color coded as follows:

red = starting point
pink = open set
green = closed set
blue = accessible but unexplored
black = inaccessible

image

Now I'm really stumped. Is there no way to do it other than to brute force all $2^{(2D-1)^2}$ combinations of topologies?

$\endgroup$
  • $\begingroup$ If a counterexample exists for the 8-neighborhood, I'd bet one exists for the 4-neighborhood. You just need to be creative. $\endgroup$ – Yuval Filmus May 19 at 19:06
  • $\begingroup$ @YuvalFilmus I'd think so, too. But I'm having trouble coming up with an example because you can't just 'cut corners'. $\endgroup$ – user200759 May 20 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.