2D grid data structure for nearest free cell

Question

Consider a 2000 x 2000 2D bool array. 100,000 elements are set to true, the rest to false.

Given a cell (x1,y1) we need to find the nearest cell (x2,y2) (by manhattan distance: abs(x1-x2) + abs(y1-y2)) that is false.

One way to do that would be to:

for (int dist = 0; true; dist++)
    for ((x2,y2) in all cells dist away from (x1,y1))
        if (!array[x2,y2])
            return (x2,y2);

In the worst case we would have to iterate through 100,000 cells before finding the free one.

Is there a data structure we could use rather than a 2D array that would allow us to perform this search quicker?

Answer 1

If the data is constant and you have many queries on it:
You might want to use a k-d tree, and look for the nearest neighbor. Insert (i,j) for each element such that arr[i][j] = false. The standard k-d tree uses euclidean distance but I think one can modify it to use manhattan distances instead..

If the data is used for one query:
You will need at least Omega(n*m) ops to read the data and insert it into any data structure - so no point in doing that - the suggested solution will outperform only the build up of any data structure.