Because of the way Manhattan distance is calculated it may seem that you can consider 2 axis's separately, a change on one has on effect of the result of the other one. However in this problem we are looking to minimize the maximum journey to any point and this has some strange effects on the maths. This is because if a point has an extreme y co-ordinate but an x co-ordinate close to the centre then it is unlikely to have the largest distance to the point P because the X component of its Manhattan distance will be small.
So all that considered using ((xmin+xmax)/2, (ymin+ymax)/2) provides a good starting place but is unlikely to be the actual answer. This is because the issue is the most extreme points, the ones closest to the corners of the square bounding your points and not the points which have a single extreme co-ordinate. Also it turns out that calculating the result is not really dependent on the starting point you use and rather than wasting time finding the min and max you might as well just use the first point.
Considering a data set
- x y
-
60 34
-
48 76
-
73 75
-
56 52
-
58 46
-
61 56
-
66 66
-
71 55
-
71 35
-
73 40
If I choose the first point (60, 34) as my first guess and calculate distances on x and y axis (and absolute) and total their absolute values
- Distance
-
x y total
-
0 0 0
-
-12 42 54
-
13 41 54
-
-4 18 22
-
-2 12 14
-
1 22 23
-
6 32 38
-
11 21 32
-
11 1 12
-
13 6 19
I can see the maximum distance is currently 54. I can also see that the minimum distance is 12.
Independently for each axis (x and y) select the rows with the the largest total and a negative axis distance and the largest total and a positive axis distance. If the axis distances are all positive or all negative select the rows with the smallest and largest axis distances.
- x axis
-
Distance
-
x y total
-
-12 42 54
-
13 41 54
-
-
y axis
-
Distance
-
x y total
-
-12 42 54
-
11 1 12
-
Get the difference of the 2 totals (smallest axis value - largest axis value) divide by 2 and if the 2 values have the same sign add on the absolute value of the smallest axis value.
x - -12 < 13 and they have different signs so (54 - 54) / 2 = 0
y - 1 < 42 and they have the same sign so (54 - 12) / 2 + abs(1) = 22
Add these values onto your original guess
60 + 0 = 60, 34 + 22 = 56
Using the new point (60, 56) re-calculate your distances
- Distance
-
x y total
-
0 -22 22
-
-12 20 32
-
13 19 32
-
-4 -4 8
-
-2 -10 12
-
1 0 1
-
6 10 16
-
11 -1 12
-
11 -21 32
-
13 -16 29
-
13 20 32
Repeat until either maximum distance stays the same (which may be with different points since there are multiple solutions) or all modifications amount to 0
Select the rows with the the largest total and a negative axis distance and the largest total and a positive axis distance.
-
x axis
-
Distance
-
x y total
-
-12 20 32
-
13 19 32
-
-
y axis
-
Distance
-
x y total
-
-12 20 32
-
11 -21 32
x - -12 < 13 and they have different signs so (32 - 32) / 2 = 0
y - -21 < 20 and they have different signs so (32 - 32) / 2 = 0
Therefore the P is (60, 56) and the maximum distance is 32 and you would compare that with d.
I am not sure that what I have written covers every corner case but it seems to me that it is the basis for solving this.