2D grid placement problem Data for the problem:


2D grid(lattice) of size NxN
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
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&lt;=i&lt;=n the will take place t_i + l_i &lt;= 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.
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$). 

If you want code, then I'm not sure where you might find it, but this site has an amazing collection of Voronoi demos written in Java (including furthest point Manhattan distance) and you might be able to adapt it for for your needs.