Minimizing the maximum Manhattan distance

Question

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<=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)

Answer 1

One dimensionality of Manhattan-distance

Let us understand the Manhattan-distance.

Here is one remarkable phenomenon. Every one of the points (0,1), (1,0), (2, -1) is 6 distance away from every one of the points (3, 4), (4, 3), (5, 2). We can imagine that the former three points correspond to $1=0+1=1+0=2+(-1)$ on the number line and that the later three points correspond to $7=3+4=4+3=5+2$ on the number line as the distance between 1 and 7 is 6. We can say Manhattan-distance on the coordinate plane is one dimensional almost everywhere.

One dimensionality of Manhattan-distance. The Manhattan-distance of two points $(x_1, y_1)$ and $(x_2, y_2)$ is either $|(x_1+y_1)-(x_2+y_2)|$ or $|(x_1-y_1)-(x_2-y_2)|$, whichever is larger. $$ d((x_1, y_1),(x_2, y_2))= \max(|(x_1+y_1)-(x_2+y_2)|, |(x_1-y_1)-(x_2-y_2)|)$$

With this understanding, it is not difficult to construct the algorithm that computes minMax, the wanted minimum of the maximum Manhattan distance of a point to the given points and count, the number of all points that reach that minMax.

Algorithm

1. Loop through all given points $(x,y)$ to compute the following.
   1. minSum, the minimum of all $x+y$.
   2. maxSum, the maximum of all $x+y$.
   3. minDiff, the minimum of all $x-y$.
   4. maxDiff, the maximum of all $x-y$.

According to the one dimensionality, we know minmax is the minimum of max((p+q)-minSum, maxSum-(p+q), (p-q)-minDiff, maxDiff-(p-q)) where (p,q) goes through all lattice points.

2. Let rangeSum = maxSum - minSum and rangeDiff = maxDiff - minDiff.
3. Let $s$ = min(rangeSum, rangeDiff) and $b$ = max(rangeSum, rangeDiff).
4. Let minMax = $b/2+1$ if both $s$ and $b$ are even and $(s-b)/2$ is odd. Otherwise, let minMax = $\lceil (b+1)/2\rceil$.

Once we have obtained the minMax, we can find all points whose maximum Manhattan-distance to points on the grid is minMax.

5. Let count = 0.
6. Run a nested loop, where i runs from (maxSum - minMax) to (minSum + minMax) and j runs from (maxDiff - minMax) to (minDiff + minMax), all inclusively. Whenever i+j is an even number, increase count by 1 since we get a point ((i+j)/2, (i-j)/2) whose maximum Manhattan-distance to the given points is minMax.

Time complexity

The only place that may run longer than $O(N)$ is the step 6. We can see that either (minSum + minMax) - (maxSum - minMax) <= 1 or (minDiff + minMax) - (maxDiff - minMax) <= 1 So the nested loops is basically one loop run at most twice. So step 6 takes at most $O(M)$ time, where $M$ is the maximum absolute value of the coordinates of the given points.

The algorithm above runs in $O(N + M)$ time, which should be faster enough to solve the original contest problem.

---

Here are two easy exercises.

Exercise 1. Prove one dimensionality of Manhattan-distance stated above. Show the algorithm above is correct.

Exercise 2. Speed up step 6 of the algorithm so that the step 6 will run in $O(1)$ time. The improved algorithm will run in $O(N)$ time.

Answer 2

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) <= 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).