Maximum minimum manhattan distance

Question

Input:

• A set of points
• Coordinates are non-negative integer type.
• Integer k

Output:

A point P(x, y) (in or not in the given set) whose manhattan distance to closest is maximal and max(x, y) <= k

My (naive) solution:

For every (x, y) in the grid which contain given set
    BFS to find closest  point to (x, y)
    ...
return maximum;

But I feel it run very slow for a large grid, please help me to design a better algorithm (or the code / peseudo code) to solve this problem.

Should I instead of loop over every (x, y) in grid, just need to loop every median x, y

P.S: Sorry for my English

EDIT:

example:

Given P1(x1,y1), P2(x2,y2), P3(x3,y3). Find P(x,y) such that min{dist(P,P1), dist(P,P2), dist(P,P3)} is maximal

Answer 1

If K is not large enough and you need to find a point with integer coordinates, you should do, as another answer suggested - Calculate minimum distances for all points on the grid, using BFS, strarting from all given points at once.

Faster solution, for large K, and probably the only one which can find a point with float coordinates, is as following. It has complexity of O(n log n log k)

Search for resulting maximum distance using dihotomy. You have to check if there is any point inside the square [0, k] X [0, k] which is at least given distance away from all points in given set. Suppose, you can check that fast enough for any distance. It is obvious, that if there is such point for some distance R, there always will be some point for all smaller distances r < R. For example, the same point would go. Thus you can search for maximum distance using binary search procedure.

Now, how to fast check for existence (and also find) a point which is at least r units away from all given points. You should draw "Manhattan spheres of radius r" around all given points. These are set of points at most r units away from given point. They are tilted by 45 degrees squares with diagonal equal to 2r. Now turn the picture by 45 degrees, and all squares will be parallel to the axis. Now you can check for existence of any point outside such squares using sweeping line algorithm. You have to sort all vertical edges of squares, and then process them one by one from left to right. Left borders will add segment mark to sweeping line, Left borders will erase it. And you have to check if there is any non marked point on the line. You can implement it using segment tree. Then, you have to check if there is any non marked point on the line inside the initial square [0,k]X[0,k].

So, again, overall solution will be binary search for r. Inside of it you will have to check if there is any point at least r units away from all given points. Do that by constructing "manhattans spheres of radius r" and then scanning them with a diagonal line from left-top corner to right-bottom. While moving line you should store number of opened spheres at each point at the line in the segment tree. between opening and closing of any spheres, line does not change, and if there is any free point there, it means, that you found it for distance r.

Binary search contributes log k to complexity. Each checking procedure is n log n for sorting squares borders, and n log k (n log n?) for processing them all.

Voronoi diagram would be another fast solution and could also find non integer answer. But it is much much harder to implement even for Manhattan measure.

Answer 2

Yes, you can do it better. I'm not sure if my solution is optimal, but it's better than yours.

Instead of doing separate BFS for every point in the grid. Do a 'cumulative' BFS from all the input points at once.

You start with 2-dimensional array dist[k][k] with cells initialized to +inf and zero if there is a point in the input for this cell, then from every point P in the input you try to go in every possible direction. The further you are from the start point the bigger integer you put in the array dist. If there is a value in dist for a specific cell, but you can get there with a smaller amount of steps (smaller integer) you overwrite it.

In the end, when no more moves can be done, you scan the array dist to find the cell with maximum value. This is your point.

I think this would work quite well in practice.

For k = 3, assuming 1 <= x,y <= k, P1 = (1,1), P2 = (1,3), P3 = (2,2)

dist would be equal in the beginning

0, +inf, +inf,

+inf, 0, +inf,

0, +inf, +inf,

in the next step it would be:

0, 1, +inf,

1, 0, 1,

0, 1, +inf,

and in the next step it would be:

0, 1, 2,

1, 0, 1,

0, 1, 2,

so the output is P = (3,1) or (3,3)

Answer 3

First try

We can turn a 2D problem into a 1D problem by projecting onto the lines y=x and y=-x. If the points are (x1,y1) and (x2,y2) then the manhattan distance is abs(x1-x2)+abs(y1-y2). Change coordinate to a u-v system with basis U = (1,1), V = (1,-1). Coords of the two points in this basis are u1 = (x1-y1)/sqrt(2), v1= (x1+y1), u2= (x1-y1), v2 = (x1+y1). And the manhatten distance is the largest of abs(u1-u2), abs(v1-v2).

How this helps. We can just work with the 1D u-values of each points. Sort by u-value, loop through points and find the largest difference between pains of points. Do the same of v-values.

Calculating u,v coords of O(n), quick sorting is O(n log n), looping through sorted list is O(n).

Alas does not work well. Fails if we have point (-10,0), (10,0), (0,-10), (0,10). Lets try a

Voronoi diagram

Construct a Voronoi diagram using Manhattan distance. This can be calculate in O(n log n) using https://en.wikipedia.org/wiki/Fortune%27s_algorithm The vertices in the diagram are points which have maximum distance from its nearest vertices. There is psudo-code for the algorithm on the wikipedia page. You might need to adapt this for Manhattan distance.