Closest unoccupied point using the Manhattan distance in $\mathbb{Z}^2$ The following is inspired by a programming question I saw meant to solve the following problem. Suppose you have a starting point $(x_0, y_0) \in \mathbb{Z}^2$ and a set of $N$ points $\{(x_1, y_1), (x_2, y_2), \ldots , (x_N, y_N) \}$ referred to as occupied. We want to find the closet unoccupied point to the starting point in terms of the Manhattan distance metric (not necessarily unique). For two points $(a_1, b_1)$, $(a_2, b_2)$, the Manhatten distance metric is given by $|a_1-a_2| + |b_1-b_2|$ (also known as the $L_1$ norm).
Here is the idea I have to solve this problem. I am not too interested in whether it's "optimal" as I have seen other solutions. Take our starting point, and compute the distance from each point to the starting point. Sort these distances using merge-sort in time $O(Nlog(N))$ giving a distance array $[d_1, d_2, \ldots, d_N]$.
Given a point, there are a fixed number of points on the grid that are a distance $k$ away from such a point. They form a diamond shape around the point.
When the distance is $0$ there is $1$ point.
When the distance is $1$, there are $4$ points (the $4$-neighborhood as they would call it in image processing)
When the distance is $2$, there are $8$ points
When the distance is $3$, there are $12$ points
This grid helps to visualize it
          * * * * * * *
          * * * * * * *
          * * * * * * *
          * * * * * * *
          * * * * * * *
          * * * * * * *
          * * * * * * *

Define $T(k) = 4k$ as the number of points of distance $k \geq 1$ away from a point using the Manhatten distance.
Taking all distances between $1$ and the largest distance in the distance array, say $M$, if for any distance $j$ with $1 \leq j \leq M$, the number of elements in the distance array with distance $j$ is smaller than $T(j)$, then necessarily there is an unoccupied point at distance $j$.
Otherwise you can take a point with distance $M+1$ as the closest unoccupied point.
In the former case, by generating all points a distance $k$ (for $k$ minimal) away, a point not in the set of $N$ points can then be found, and the closest point is given.
Is this algorithm correct?
 A: As far as I can tell, your algorithm seems fine.
Here are some elements for a somewhat more formal reasoning:
For any $ p_0\in \mathbb{Z}^2$ and  $k \in \mathbb{N}$, let $S_k(p_0) = \{p\in \mathbb{Z}^2; ||p-p_0||_1 = k\}$ denote the set of points of the grid at distance exactly $k$ from $p_0$.
Proposition: $\forall p_0\in \mathbb{Z}^2$, $\forall k \in \mathbb{N}$, $|S_k(p_0)|=4k$.
Proof: Let $p_0=(x_0, y_0)$ and $p=(x,y) \in S_k(p_0)$ .
Let $l=|x-x_0|$, for any fixed $1\leq l \leq k - 1$ and $x_0$, there exist two possible values of $x$ ($x_0\pm l$) and likewise two values for $y$ (as $|y-y_0|=k-l$). For $l=0$ there are two values for $y$ but only one for $x$ and for $l=k$, there are two for $x$ but only one for $y$. In the end, there exist $4(k-1) + 2 + 2 = 4k$ distinct points at distance $k$ from $p_0$.
Then, let $n_k$ be the number of occupied points at distance $k$ from $p_0$. All that is left to do is to apply some derivative of the pigeonhole principle on each $S_k$, in increasing order of $k$. Once the smallest distance $k$ for which at least one point is unoccupied is found, finding an actual unoccupied point can be done by running an exhaustive search.
Some additional thoughts:

*

*The $n_k$ are all you need rather than the sorted array of the distances, this is interesting as finding the $n_k$ can be done in linear time from the (unsorted) array of the distances to $p_0$.


*While searching up to the largest of those distances $M$ guarantees that one unoccupied point $p$ will be found, the significant metric for how far from $p_0$ $p$ will be is $N$. Indeed, If $N$ is less than $\sum_{l=0}^k 4l = 2k(k+1)$ for some $k$, an unoccupied point can always be found at distance at most $k$ (this results from applying the pigeonhole principle on the set $S'_k(p_0)= \bigcup_{0\leq l\leq k}S_l(p_0)$ of points at distance at most $k$ from $p_0$).


*In the end, it takes $O(N)$ to compute the distance array, $O(N)$ to derive the $n_k$, $O(\sqrt{N})$ (worst-case) to find the minimal distance for an unoccupied point and $O(\sqrt{N})$ to find said unoccupied point. The whole pipeline runs in linear time overall.
