Minimizing the maximum Manhattan distance
Manhattan-distance balls are square and aligned with the diagonals, which makes this problem much simpler than the Euclidean equivalent.

Find an input point P with maximum x+y, an input point Q with minimum x+y, an input point R with maximum x-y, and an input point S with minimum x-y. The minimum maximum distance d is the maximum of ceiling(((P.x+P.y) - (Q.x+Q.y))/2) and ceiling(((R.x-R.y) - (S.x-S.y))/2) or sometimes that quantity plus one. Accordingly, for each center C, we can compute the bounds on C.x+C.y and C.x-C.y so that (P.x+P.y) - (C.x+C.y) &lt;= d and similarly for Q, R, S. Then there's some simple formula to count the points in that rotated rectangle. If the count is zero, increase d and try again.

The overall running time is O(N).