<p>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. </p>

<p>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.  </p>

<p>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$). </p>

<p>If you want code, then I'm not sure where you might find it, <a href="http://www.nirarebakun.com/voro/efpmancli.html" rel="nofollow">but this site has an amazing collection of Voronoi demos</a> written in Java (including furthest point Manhattan distance) and you might be able to adapt it for for your needs. </p>

CC BY-SA 3.0
2011-11-16T08:35:18.233Z
maybe there is some paper or book that gives at least a pseudo code?
YAKOVM
CC BY-SA 3.0
2011-11-16T16:25:21.083Z
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
CC BY-SA 3.0
2011-11-15T23:12:46.197Z
2011-11-15T23:12:46.197Z
Suresh Venkat
<p>Data for the problem:</p>

<ol>
<li>2D grid(lattice) of size NxN</li>
<li><p>n nodes placed on the grid:node_1,node_2,…node_n
Each of nodes contain some data:</p>

<p>a.   node_i is presented by 3 parameters (x_i,y_i,t_i)</p>

<p>b.       x_i and y_i represent the coordinates on the grid</p>

<p>c.       t_i represent the time when the node`s data  is ready</p></li>
<li><p>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</p></li>
</ol>

<p>For example please take a look for the following examples when n = 2</p>

<p>Node_1 :x_1 = 0,y_1 = 0,t_1 =1</p>

<p>Node_2 :x_2 = 4,y_2= 3,t_2 = 4</p>

<p>Node_2 :x_3 =?,y_3 = ?,t_3 = 6</p>

<p>-> x_3 = 3?,y_3= 2</p>

<p>Node_1 :x_1 = 0,y_1 = 0,t_1 =0</p>

<p>Node_2 :x_2 = 4,y_2= 4,t_2 = 0</p>

<p>Node_2 :x_3 =?,y_3 = ?,t_3 = 4</p>

<p>-> x_3 = 2?,y_3= 2</p>

<p>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.</p>

CC BY-SA 3.0
2011-11-15T22:53:18.267Z
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
<ds.algorithms><graph-theory><scheduling><lattice><embeddings>
2D grid placement problem
YAKOVM
# 2D grid placement problem

(Asked by: username_0 on 2011-11-15)

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.

**Tags:** ds.algorithms, graph-theory, scheduling, lattice, embeddings

> **Comments:**
> **username_1**: 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  

---

## 1 answers

### Answer by username_1 on 2011-11-15. Score: 4 | Accepted answer

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](http://www.nirarebakun.com/voro/efpmancli.html) written in Java (including furthest point Manhattan distance) and you might be able to adapt it for for your needs.

> **Comments:**
> **username_0**: maybe there is some paper or book that gives at least a pseudo code?  
> **username_1**: 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.  

---

