Updating the Influence List

After updating the results, we may have to remove $q$ from the influence lists of cells $c$ whose $mindist(c,q)$ is greater than current $q.dist_k$ . Consider the running example of Fig.  where after the update of results, both the shaded and striped cells contain $q$ in their influence lists whereas only the shaded cells can actually influence the query. So we need to remove $q$ from the influence lists of all striped cells.

Figure: Updating Influence Region

[before update]

[after update]

A straightforward approach to update influence lists is to first identify a square that contains all the shaded and striped cells. Then, we could check $mindist(c,q)$ of all the cells $c$ in the square and could delete the cells for which $mindist(c,q) > dist_k$ . However, this approach requires computing $mindist$ of many cells which can be avoided. We use CircularTrip to efficiently update the influence lists as follows: First we call CircularTrip with radius $r=q'.dist_k$ and mark all the returned cells as shown shaded in Fig. . Then, we identify a square that contains all the shaded and striped cells. The side length of the square can be at most $max\{q_{pre}.dist_k,2\times(dist(q_{pre},q_{cur})+q_{cur}.dist_k)\}$ . Now we remove $q$ from the cells contained in the square that lie outside the marked circle. To do this, for each row of the square, we start processing the cells from the left most cell towards the right end cell of the square. For each cell $c$ , we delete $q$ from the influence list. We stop if a cell $c$ is marked or if it resides outside of the square. If the cell $c$ is marked, we continue deleting $q$ from the influence lists from the cells in the same row from right end to left end unless some marked cell is found. The update of influence lists completes when all rows are processed in the way described above. Note that this approach requires computing $mindist$ of only the shaded cells of Fig. .s