ArcTrip

First we define $minadist(q,c,\langle \theta_1,\theta_2\rangle)$ that is minimum angular distance of a cell $c$ from $q$ and then we will give formal definition of ArcTrip.

Minimum angular distance ( $minadist(q,c,\langle \theta_1,\theta_2\rangle)$ ): The minimum angular distance between a cell $c$ and the query point $q$ is Euclidean distance from $q$ to the nearest boundary of the portion of $c$ that lies between angle range $\langle \theta_1,\theta_2 \rangle$ . Fig.  clarifies the definition where $minadist$ values of $c_1$ and $c_2$ are same as their $mindist$ whereas $minadist$ of $c_3$ is the minimum distance of the shaded area of $c_3$ from $q$ . Any cell that completely lies outside the angle range has $minadist=\infty$ . i.e; $minadist(q,c_4,\langle \theta_1,\theta_2\rangle)=\infty$ .

Now we define ArcTrip( $q,r,\langle \theta_1,\theta_2\rangle)$ : given a radius $r$ and an angle range $\langle \theta_1,\theta_2 \rangle$ , ArcTrip returns every cell $c$ that intersects the circle of radius $r$ with center at $q$ and has $minadist(q,c,\langle \theta_1,\theta_2\rangle)$ smaller than $r$ . Consider the example of Fig. , ArcTrip($q$ , $r,\theta_1,\theta_2$ ) returns all the shaded cells.

Figure: ArcTrip

ArcTrip algorithm is similar to CircularTrip. The algorithm starts with the cell $c_{start}$ that intersects the circle and lies at angle $\theta_2$ . The cell $c_{start}$ is shown in Fig. . Mathematically, $c_{start}=c[i,j]$ where $i= \lfloor (q.x + r.Cos\theta_2) / \delta \rfloor$ and $j= \lfloor q.y + r.Sin\theta_2 / \delta \rfloor$ ); The direction $D_{cur}$ is selected according to the quadrant in which $c_{start}$ lies. Fig.  , shows $D_{cur}$ for different quadrants with jumbo arrows. In the example of Fig. , $D_{cur}$ is set as down. The algorithm continues exactly same as CircularTrip and terminates as soon as the next cell that intersects the circle lies outside the range $\langle \theta_1,\theta_2 \rangle$ .

Figure: The Special Cell $c_{spe}$ is Always the Adjacent Cell of $c$ in $D_{opp}$

Note from Fig. , if we start from $c_{start}$ as mentioned above, we may miss a cell $c_{spe}$ that should have been returned by ArcTrip. We prove next that this special cell $c_{spe}$ is always adjacent to $c_{start}$ in direction opposite to $D_{cur}$ . To address this issue, we always first check whether the cell $c_{spe}$ should be inserted in $C$ or not depending on whether it lies in angle range $\langle \theta_1,\theta_2 \rangle$ or not. If it lies in the angle range we include it in result otherwise we ignore it (i.e; line 4 - 5 of Algorithm ).

Lemma

Let $c_{start}$ be the starting cell of ArcTrip as defined earlier and $D_{opp}$ be the opposite direction of $D_{cur}$ . The only cell ArcTrip can miss is $c_{spe}$ that is always the adjacent cell to $c_{start}$ in direction $D_{opp}$ .

Proof:

It can be immediately verified that the $c_{spe}$ is one of the four cells adjacent to $c_{start}$ (in Fig.  $c_{start}$ is shown as $c$ ). The cells in direction $D_{cur}$ and $D_{next}$ will be checked during execution of ArcTrip and will be inserted if intersect the circle. So $c_{spe}$ can only be the cell either in direction $D_{opp}$ or the remaining direction $D_{rem}$ .

Let $c_{opp}$ and $c_{rem}$ be the adjacent cells to $c_{start}$ in direction $D_{opp}$ and $D_{rem}$ , respectively. It can be immediately verified that $minadist(q,c_{rem},\langle \theta_1,\theta_2\rangle)$ is always greater than $r$ (otherwise it would have been the starting cell $c_{start}$ ), so ArcTrip does not need to check it. We are left only with $c_{opp}$ and hence it is $c_{spe}$ .

Algorithm  presents the implementation of ArcTrip. Note that CircularTrip can be considered a special case of ArcTrip where angle range is the whole space. More specifically we can say that CircularTrip($q,r$ ) is exactly same as ArcTrip( $q,r,\langle -180^\circ,180^\circ \rangle$ ).