1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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 $\endgroup$ – Suresh Venkat Nov 15 '11 at 22:53
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ maybe there is some paper or book that gives at least a pseudo code? $\endgroup$ – Yakov Nov 16 '11 at 8:35
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Nov 16 '11 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.