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 $(x,y)$ must exist. The same argument applies to points with the same $y$-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 NO. After both passes, the answer is YES 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)$.