Recognizing Convex Grid Graphs

Let $S$ be the set of given points. It is enough to verify all three conditions below.

• For every fixed $x$-coordinate, the occurring $y$-coordinates are consecutive without gaps.
• For every fixed $y$-coordinate, the occurring $x$-coordinates are consecutive without gaps.
• The graph is connected.

First, these conditions are necessary. Consider two points $(x,a)$ and $(x,b)$ with the same $x$-coordinate. Their Manhattan distance is $|a-b|$. A path of exactly this length cannot use a horizontal edge, so every intermediate lattice point must exist. The same argument applies to points with the same -coordinate. The graph must also be connected because every pair must have a finite graph distance.

Now suppose that all three conditions hold. Choose a shortest path between any two vertices $u$ and $v$. Assume that the path uses both rightward and leftward edges. Then it contains a subpath whose endpoints have the same $x$-coordinate and whose interior contains at least one horizontal edge. Since all points between the endpoints on that fixed $x$-coordinate exist, the endpoints can be connected directly by a vertical path. This direct path is shorter than the chosen subpath, contradicting shortestness. Therefore the $x$-coordinate changes in only one direction along a shortest path. By the same argument, the $y$-coordinate also changes in only one direction. Hence the path length is exactly the Manhattan distance.

For the implementation, sort the point indices by $(x,y)$. For every adjacent pair with the same $x$-coordinate, verify that their $y$-coordinates differ by exactly $1$, and unite them in a DSU. Then sort by $(y,x)$ and perform the symmetric check. If any gap exists, the answer is . After both passes, the answer is exactly when all points belong to one DSU component.

The time complexity is $O(N\log N)$ because of the two sorts, and the memory complexity is $O(N)$.