# 2D grid placement problem

Data for the problem:

1. 2D grid(lattice) of size NxN
2. n nodes placed on the grid:node_1,node_2,…node_n Each of nodes contain some data:

a. node_i is presented by 3 parameters (x_i,y_i,t_i)

b. x_i and y_i represent the coordinates on the grid

c. t_i represent the time when the node`s data is ready

3. Given a node_(n+1) and t_(n+1) I should find x_(n+1) and y_(n+1): Such that, if we define l_i = (x_(n+1)-x_i) +( y_(n+1)-y_i) , For every 1<=i<=n the will take place t_i + l_i <= t_(n+1) If the above is impossible the max( t_(n+1) – (t_i + l_i)) should be minimized

For example please take a look for the following examples when n = 2

Node_1 :x_1 = 0,y_1 = 0,t_1 =1

Node_2 :x_2 = 4,y_2= 3,t_2 = 4

Node_2 :x_3 =?,y_3 = ?,t_3 = 6

-> x_3 = 3?,y_3= 2

Node_1 :x_1 = 0,y_1 = 0,t_1 =0

Node_2 :x_2 = 4,y_2= 4,t_2 = 0

Node_2 :x_3 =?,y_3 = ?,t_3 = 4

-> x_3 = 2?,y_3= 2

I need general algortithm for finding x_(n+1) and y_(n+1).Does anyone have some clue how to solve such a problem. Thank you.

• Let me attempt a translation of your problem. You're given a collection of points on the grid, and associated with each point $i$ is a radius $r_i = t_{n+1}-t_i$. You wish to find a point such that its distance from the furthest ball is minimized. All balls are with respect to the manhattan/grid distance (i.e $\ell_1$), and the distance to a ball is 0 if you're inside it – Suresh Venkat Nov 15 '11 at 22:53

If I understand your problem correctly, it seems like you're looking to examine a furthest-point weighted Voronoi diagram under the Manhattan ($\ell_1$) distance. The transformation is as follows.
For each point $p_i$ on the grid, define the distance function $$d_i(x) = \max(0, \|x - p_i\|_1 - (t_{n+1}-t_i))$$ Then $d_i(x)$ is the (truncated) distance of $x$ from the ball of radius $t_{n+1}-t_i$ around $p_i$ under the $\ell_1$ distance.
You want to find $$x^* = \arg \min \max_i \ d_i(x)$$ which can be obtained by computing the furthest-point weighted Voronoi diagram under the $\ell_1$ distance (the weighted part is because of the offset associated with the $t_i$).
• You can find papers that describe the furthest point V.D under $\ell_1$. the weighted case makes things a little more work, but should be doable. – Suresh Venkat Nov 16 '11 at 16:25