Minimizing the maximum Manhattan distance Given N points on a grid, find the number of points, such that the smallest maximal Manhattan distance from these points to any point on the grid is minimized. Also, determine the distance itself.

The points are inside a grid, –10000 ≤ Xi ≤ 10000 ; –10000 ≤ Yi ≤ 10000,  N&lt;=100000.

In the example below the points are (1, 1), (6,1), (6,6), (3,4) and the smallest maximal Manhattan distance (equal to 5) is achieved from points (4,3), (5,2) (marked with E).



Is there an efficient algorithm to solve the problem?
The restrictions are quite large so the brute force approach wouldn't work.

Edit: problem: http://varena.ro/problema/examen (RO language)
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).