CircularTrip on 2D Grid

To collect a round of cells, CircularTrip starts from the cell $c_{start}$ that is intersected by the given circle and lies left to $c^q$ . CircularTrip starts checking the cells along the circle in direction $D_{cur}$ which is initially set as up. In order to make a clock-wise trip, the $D_{cur}$ needs to be changed from up to right to down to left to up. The direction $D_{next}$ always holds the next direction of $D_{cur}$ .

Figure: CircularTrip

Without loss of generality, consider cell $c$ intersected by the circle which locates in the upper-left quadrant as shown in Fig. . The key fact is that the next cell intersected by the circle (i.e., the cell in which the arc is connected to one in $c$ ) is the adjacent cell either above $c$ (i.e., the cell $c_c$ that is next cell in direction $D_{cur}$ ) or right to $c$ (i.e., the $c_N$ that is next cell in direction $D_{next}$ ). This is because the outgoing circle crosses either the upper boundary or the right boundary of $c$ . These two adjacent cells, $c_c$ and $c_N$ , are called candidate adjacent cells of $c$ . To collect the next cell intersected by the circle, CircularTrip only needs to examine one of the candidate adjacent cells (i.e; check its $mindist(c,q)$ with the given radius $r$ ).

Algorithm  presents the implementation of CircularTrip algorithm. Though any cell can be selected as $c_{start}$ but in our implementation the left most cell of the round (as shown in Fig. ) is selected. CircularTrip examines the cells clockwise along the given circle until $c_{start}$ is encountered again. When the currently being examined cell $c$ is at the maximum level in $D_{cur}$ , the directions to find its candidate adjacent cells are updated accordingly (i.e., line 10 - 12). The cells when the directions $D_{cur}$ and $D_{next}$ are changed are shown dark shaded in Fig. . Moreover, for some of the cells, $D_{cur}$ and the $D_{next}$ are shown with solid and hollow arrows, respectively.

Lemma 1

The total cost of CircularTrip to collect a round $C$ of cells is to compute $mindist(c,q)$ of $\vert C\vert$ cells, where $\vert C\vert$ is the number of cells in round $C$ .

Proof

Let $c$ be the current cell being examined and $c_c$ and $c_N$ be the cells next to $c$ in direction $D_{cur}$ and $D_{next}$ , respectively. In order to prove Lemma , it is sufficient to prove that algorithm needs to compute $mindist$ of only one of $c_c$ or $c_N$ from $q$ in order to confirm the next intersected cell.

Figure: Next Intersected Cell is Either $c_c$ or $c_N$

As can be seen from Fig. , selection of $D_{cur}$ and $D_{next}$ is made so that following two conditions hold.

equation 1: $mindist(c_N,q)<mindist(c,q)<mindist(c_c,q)$
equation 2: $maxdist(c_N,q)<maxdist(c,q)<maxdist(c_c,q)$
As cell $c$ intersects the circle, it satisfies that

equation 3: $mindist(c,q)< r\leq maxdist(c,q)$
From equations 1,2 and 3, it can be concluded that
equation 4: $mindist(c_N,q)<r<maxdist(c_c,q)$

CircularTrip computes $mindist(c_c,q)$ , and if $mindist(c_c,q)<r$ , then $c_c$ intersects the circle as can be inferred in conjunction with equation 4 that $mindist(c_c,q)<r< maxdist(c_c,q)$ .

If $mindist(c_c,q)\geq r$ , then it infers that $maxdist(c_N,q)\geq r$ because $mindist(c_c,q)=maxdist(c_N,q)$ . So CircularTrip can confirm $c_N$ as next intersected cell without computing its distance from $q$ because for cell $c_N$ in conjunction with equation 4, it is confirmed that $mindist(c_N,q)<r\leq maxdist(c_N,q)$ .