Counting Unit Circular Arc Intersections

Consider a short blue arc $s_b$. Let $D_1$ and $D_2$ be the two unit disks centered at the two endpoints of $s_b$, respectively. We call the region of $D_1$ that is not in $D_2$ a lune; similarly, region of $D_2$ that is not in $D_1$ is also a lune. We use $lune(s_b)$ refer to the union of the two lunes (for simplicity, we consider $lune(s_b)$ as a single lune defined by $s_b$), i.e., $lune(s_b)=D_1\cup D_2-D_1\cap D_2$, the symmetric difference of $D_1$ and $D_2$ (e.g., the grey area in Fig. 3). By definition, a point is in $lune(s_b)$ if and only if the unit disk centered at the point contains exactly one endpoint of $s_b$, implying that the unit circle centered at the point intersects $s_b$ exactly once. Observation 3 is crucial to our algorithm for counting type (3.1.1) intersections in Lemma 4.

Let $p$ be the center of $s_r$ and $D$ be the underlying disk of $s_r$.

If $s_r$ intersects $s_b$ exactly once, then one endpoint of $s_b$ must be inside $D$ while the other is outside $D$. Therefore, $p$ must be in $lune(s_b)$. Below we prove the other direction of the observation.

If $p$ is in $lune(s_b)$, then by the definition of $lune(s_b)$, one endpoint of $s_b$ is in $D$ while the other is not. Hence, $s_b$ must cross $\partial D$ at exactly one point, say, $q$, which is the only intersection between $s_b$ and $\partial D$. As $s_b$ is in the cell $\tau$, $q\in \tau$. Since $q\in \partial D$, we obtain that $q\in \partial D\cap \tau$. Further, since $s_r$ is a long full arc, we have $s_r=\partial D\cap \tau$. Hence, $q\in s_r$. This implies that $q\in s_r\cap s_b$. Since $s_r\in \partial D$ and $s_b$ and $\partial D$ has exactly one intersection, we conclude that $s_b$ and $s_r$ has exactly one intersection. $◀$

For notational convenience, let $n=n_{\tau }$ and $m=m_{\tau }$ in this proof. Recall that centers of red arcs are in the cell $C_r\in 𝒞$. For each short blue arc $s_b$, since the radius of $s_b$ is $1$ and $C_r$ is a square cell of the side-length $1/\sqrt{2}$, the boundary of the intersection of $C_r$ and $lune(s_b)$ has at most four circular arcs (which are on the unit circles centered at the two endpoints of $s_b$, respectively); let $H$ be the set of these circular arcs defined by all short blue arcs. Hence, $|H|=O(m)$. By Observation 3, it suffices to compute the number of lunes $lune(s_b)$ containing the center of each long red arc. Let $L$ denote the set of the lunes $lune(s_b)$ of all short blue arcs $s_b$.

We build a hierarchical $(1/r)$-cutting ${\mathrm{\Xi }}_0,{\mathrm{\Xi }}_1,\mathrm{\dots },{\mathrm{\Xi }}_k$ on the arcs of $H$, with $r=m/\log m$. This can be done in $O(mr)$ time by Theorem 1. For each cell $\sigma \in {\mathrm{\Xi }}_i$, $1\le i\le k$, we define $m_{\sigma }$ as the number of lunes of $L$ that contain $\sigma$ but do not contain the parent cell of $\sigma$ in ${\mathrm{\Xi }}_{i-1}$ (i.e., the boundary of the lune crosses the parent cell). We can compute $m_{\sigma }$ for all cells $\sigma \in {\mathrm{\Xi }}_i$, for all $i=1,2,\mathrm{\dots },k$, as follows.

Recall that the algorithm of Theorem 1 for computing the hierarchical cutting also produces the sets $H_{\sigma }$ for all cells $\sigma \in {\mathrm{\Xi }}_i$, $0\le i\le k$, where $H_{\sigma }$ is the subset of arcs of $H$ crossing $\sigma$, in $O(mr)$ time. As discussed in Section 2, the total size of these sets for all cells is $O(mr)$.

Next, we show that the values $m_{\sigma }$ for all cells $\sigma \in {\mathrm{\Xi }}_i$, $1\le i\le k$ can be computed in $O(mr)$ time using the sets $H_{\sigma }$. Define $L(\sigma )$ as the subset of lunes of $L$ that contain $\sigma$ but does not contain the parent cell of $\sigma$. Hence, $m_{\sigma }=|L(\sigma )|$. Observe that one of the bounding arcs of each lune of $L(\sigma )$ must cross ${\sigma }^{\prime }$, where ${\sigma }^{\prime }$ is the parent of $\sigma$ in ${\mathrm{\Xi }}_{i-1}$. This implies that we can compute $L(\sigma )$ and thus $m_{\sigma }$ using $H_{{\sigma }^{\prime }}$ as follows. For each arc $s\in H_{{\sigma }^{\prime }}$, we check whether the lune of $L$ bounded by $s$ contains $\sigma$; if yes, we add the lune to $L(\sigma )$. Since each cell of the hierarchical cutting has $O(1)$ child cells, the above algorithm for computing $m_{\sigma }$ for all cells $\sigma \in {\mathrm{\Xi }}_i$, $1\le i\le k$, runs in time linear in the total size of $H_{\sigma }$ for all cells $\sigma \in {\mathrm{\Xi }}_i$, $0\le i\le k$, which is $O(mr)$ as explained above. As such, after the hierarchical cutting is computed, $m_{\sigma }$ for all cells $\sigma \in {\mathrm{\Xi }}_i$, $1\le i\le k$, can be computed in $O(mr)$ time.

For each long red arc $s$, we locate the cell ${\sigma }_i$ of ${\mathrm{\Xi }}_i$ containing $q$ for each $1\le i\le k$, where $q$ is the center of $s$; we add all these values $m_{{\sigma }_i}$ to a total count $m_s$ (initially, $m_s=0$). Finally, for the cell $\sigma \in {\mathrm{\Xi }}_k$, for each arc $s^{\prime }\in H_{\sigma }$, we check whether the lune of $L$ bounded by $s^{\prime }$ contains $q$; if yes, we increases $m_s$ by one. It is not difficult to see the value $m_s$ thus obtained is equal to the number of lunes of $L$ containing $q$. Since $|H_{\sigma }|=O(m/r)=O(\log m)$ for any $\sigma \in {\mathrm{\Xi }}_k$ and $k=O(\log r)$, the time of the above algorithm for computing $m_s$ is $O(\log m)$. We apply the above algorithm for each long red arc, after which the number of type (3.1.1) intersections is computed. As there are at most $n$ long red arcs, the total time of the algorithm is $O(mr+n\log m)$, which is $O(m^2/\log m+n\log m)$ as $r=m/\log m$. $◀$

We now discuss type (3.1.2) intersections. Consider a long red partial arc $s_r$. Recall that the center of $s_r$ is in the square cell $C_r$. By property (2) of $𝒞$, the two cells $C_r$ and $C$ are separated by an axis-parallel line. Depending on whether the line is horizontal or vertical, without loss of generality, we assume that $C_r$ is either below $C$ or to the right of $C$. Recall that the pseudo-trapezoid $\tau$ is in $C$, and typically the upper (resp., lower) side of $\tau$ is a unit circular arc while both the left and right sides of $\tau$ are vertical segments. Since $s_r$ is a partial arc, the underlying circle $\alpha (s_r)$ intersects $C$ at another arc, denoted by $s_r^{\prime }$; we call $s_r^{\prime }$ the coupled arc of $s_r$ (and $s_r$ is also the coupled arc of $s_r^{\prime }$).

Consider a type (3.1.2) intersection between a long red partial arc $s_r$ and a short blue arc $s_b$. We further partition type (3.1.2) intersections into two types: (3.1.2.1) $s_b$ does not intersect the coupled arc $s_r^{\prime }$ of $s_r$; (3.1.2.2) $s_b$ intersects $s_r^{\prime }$ (since $s_r$ and $s_r^{\prime }$ are on the same circle and $s_b$ intersects $s_r$, $s_b$ intersects $s_r^{\prime }$ exactly once in this case). We will present algorithms to count type (3.1.2.1) and type (3.1.2.2) intersections separately.

For each short-blue arc $s_b$, we use $lun{e}^{\prime }(s_b)$ to denote the region of the plane outside the union of the two unit disks centered at the two endpoints of $s_b$.

Recall that $C_r$ is either below $C$ or to the right of $C$. Below we give observations for both cases, which lead to algorithms for counting type (3.1.2.1) and type (3.1.2.2) intersections.

Suppose $C_r$ is below $C$. Then, $s_r$ and $s_r^{\prime }$ are both on the upper semicircle of $\alpha (s_r)$ (e.g., see Fig. 4). Thus, both $s_r$ and $s_r^{\prime }$ are $x$-monotone, and $s_r$ is either to the left or to the right of $s_r^{\prime }$. Let $z(s_r)$ denote the endpoint of $s_r$ closer to $s_r^{\prime }$, e.g., $z(s_r)$ is the right (resp., left) endpoint of $s_r$ if $s_r$ is to the left (resp., right) of $s_r^{\prime }$. We have the following observation for type (3.1.2.1) and type (3.1.2.2) intersections. See the full paper for the proof.

If $C_r$ is to the right of $C$, $s_r$ and $s_r^{\prime }$ are both in the left semicircle of $\alpha (s_r)$; e.g., see Fig. 5. Thus, both $s_r$ and $s_r^{\prime }$ are $y$-monotone, and $s_r$ is either above or below $s_r^{\prime }$. Let $z(s_r)$ denote the endpoint of $s_r$ closer to $s_r^{\prime }$, e.g., $z(s_r)$ is upper (resp., lower) endpoint of $s_r$ if $s_r$ is below (resp., above) $s_r^{\prime }$. We have the following observation, which is similar in spirit to Observation 5.

Based on Observations 5 and 6, Lemmas 7 and 8 below compute the numbers of type (3.1.2.1) and type (3.1.2.2) intersections, respectively. Hence, the number of type (3.1.2) intersections can be computed in $O(m_{\tau }^2/\log m_{\tau }+n_{\tau }{\log }^2{m}_{\tau })$ time.

We assume that $C_r$ is below $C$ and the other case where $C_r$ is right of $C$ can be handled similarly. Our algorithm will be based on Observation 5(1). The algorithm is similar to Lemma 4 but with an additional level data structure. In what follows, we follow the notation in the proof of Lemma 4 and only point out the differences. For notational convenience, we let $n=n_{\tau }$ and $m=m_{\tau }$ in this proof.

We follow the same algorithm as in Lemma 4 but set $r=m/{\log }^{2}m$. Recall that for each cell $\sigma \in {\mathrm{\Xi }}_i$, $i=1,2,\mathrm{\dots },k$, we have defined a subset $L(\sigma )\subseteq L$ consisting of the lunes of $L$ that contain $\sigma$ but do not contain the parent cell of $\sigma$ in ${\mathrm{\Xi }}_{i-1}$. The total size of all these subsets is $O(mr)$. For each subset $L(\sigma )$, for each $lune(s_b)\in L(\sigma )$, since $lune(s_b)$ contains $\sigma$, all unit disks centered in $\sigma$ contain exactly the same endpoint of $s_b$ and let $p(s_b,\sigma )$ denote the other endpoint; we use $P(\sigma )$ to denote set of all these endpoints $p(s_b,\sigma )$ for all $lune(s_b)\in L(\sigma )$. Note that $|P(\sigma )|=|L(\sigma )|$. We explicitly maintain $P(\sigma )$. Computing these subsets $P(\sigma )$ for all cells can be done in $O(mr)$ time by using the sets $L(\sigma )$. We further sort each set $P(\sigma )$ by their $x$-coordinates. As the total size of $P(\sigma )$ for all cells $\sigma$ is $O(mr)$, the sorting for $P(\sigma )$ of all cells $\sigma$ can be done in $O(mr\log m)$ time.

For each long red arc $s_r$, we first check whether it is a partial arc (this can be done in $O(1)$ time). If not, we ignore it. If yes, we proceed as follows. Without loss of generality, we assume that $s_r$ is to the left of $s_r^{\prime }$ and thus $z(s_r)$ is the right endpoint of $s_r$. Let $q$ be the center of $s_r$. We locate the cell ${\sigma }_i$ of ${\mathrm{\Xi }}_i$ containing $q$ for each $1\le i\le k$. For each ${\sigma }_i$, according to Observation 5(1), we perform binary search on the sorted list of $P(\sigma )$ to find the number of points of $P(\sigma )$ to the left of $z(s_r)$, and let $m_{{\sigma }_i}$ denote this number. We add all these values $m_{{\sigma }_i}$ to a total count $m_{s_r}$ (initially, $m_{s_r}=0$). Finally, for the cell $\sigma \in {\mathrm{\Xi }}_k$, for each arc $s^{\prime }\in H_{\sigma }$, we do the following. Note that $s^{\prime }$ is an arc of $lune(s_b)$ for a short blue arc $s_b$. We check in $O(1)$ time whether $s_r$ and $s_b$ form a type (3.1.2.1) intersection; if yes, we increase $m_{s_r}$ by one. The value $m_{s_r}$ thus obtained is equal to the number of type (3.1.2.1) intersections involving $s_r$. The time for computing $m_{s_r}$ is $O({\log }^{2}m)$. We apply the above algorithm for each long red arc, after which the number of type (3.1.2.1) intersections is computed. The total runtime is $O(mr\log m+n{\log }^{2}m)$, which is $O(m^2/\log m+n{\log }^{2}m)$ as $r=m/{\log }^{2}m$. $◀$

We assume that $C_r$ is below $C$ and the other case where $C_r$ is right of $C$ can be handled similarly. Our algorithm will be based on Observation 5(2). For notational convenience, let $n=n_{\tau }$ and $m=m_{\tau }$ in this proof.

We still follow the algorithm in the Lemma 4 but set $r=m/{\log }^{2}m$ and use $lun{e}^{\prime }(s_b)$ to replace $lune(s_b)$. Note that the intersection of $C_r$ and $lun{e}^{\prime }(s_r)$ is still bounded by at most two circular arcs (other than the boundary of $C_r$). Let $H$ be the set of all these circular arcs for all short blue arcs. Let $L$ denote the set of $lun{e}^{\prime }(s_b)$ of all short blue arcs $s_b$. Next, we build a hierarchical cutting for $H$ in the same way as in the proof of Lemma 4. We define $L(\sigma )$ in the same way. Let $B(\sigma )$ denote the set of short blue arcs $s_b$ with $lun{e}^{\prime }(s_b)\in L(\sigma )$. Using $L(\sigma )$, we can obtain $B(\sigma )$ for all cells $\sigma \in {\mathrm{\Xi }}_i$, $i=1,2,\mathrm{\dots },k$, in $O(mr)$ time. For each arc $s_b\in B(\sigma )$, it defines an interval $[x_1(s_b),x_2(s_b)]$, where $x_1(s_b)$ and $x_2(s_b)$ are the $x$-coordinates of the left and right endpoints of $s_b$, respectively; let $I(\sigma )$ denote the set of all these intervals for all arcs of $B(\sigma )$. We build an interval tree (Section 10.1 [5]) on the intervals of $I(\sigma )$ in $O(|I(\sigma )|\log |I(\sigma )|)$ time so that given a query $x$-coordinate $x$, we find in $O(\log |I(\sigma )|)$ time the number of intervals of $I(\sigma )$ containing $x$. As $|I(\sigma )|=O(m)$ and the total size of the sets $I(\sigma )$’s of all cells in the cutting is $O(mr)$, the total time for building the interval trees is $O(mr\log m)$.

For each long red arc $s_r$, we first check whether it is a partial arc (this can be done in $O(1)$ time). If not, we ignore it. If yes, we proceed as follows. Without loss of generality, we assume that $s_r$ is to the left of $s_r^{\prime }$ and thus $z(s_r)$ is the right endpoint of $s_r$. Let $q$ be the center of $s_r$. We locate the cell ${\sigma }_i$ of ${\mathrm{\Xi }}_i$ containing $q$ for each $i=1,2,\mathrm{\dots },k$. For each ${\sigma }_i$, we query the interval tree of $I({\sigma }_i)$ to find number of intervals of $I({\sigma }_i)$ containing $z(s_r)$; let $m_{{\sigma }_i}$ denote this number. We add all these values $m_{{\sigma }_i}$ to a total count $m_{s_r}$ (initially, $m_{s_r}=0$). Finally, for the cell $\sigma \in {\mathrm{\Xi }}_k$, for each arc $s^{\prime }\in H_{\sigma }$, we do the following. Let $s_b$ be the short-blue arc such that $s^{\prime }$ is an arc of $lun{e}^{\prime }(s_b)$. We check whether $s_r$ and $s_b$ form a type (3.1.2.1) intersection, which can be done in $O(1)$ time; if yes, we increases $m_{s_r}$ by one. The value $m_{s_r}$ thus obtained is equal to the number of type (3.1.2.2) intersections involving $s_r$. The time for computing $m_{s_r}$ is $O({\log }^{2}m)$. We apply the above algorithm for each long red arc, after which the number of type (3.1.2.2) intersections is computed. The total time of the algorithm is $O(mr\log m+n{\log }^{2}m)$, which is $O(m^2/\log m+n{\log }^{2}m)$ as $r=m/{\log }^{2}m$. $◀$

We first apply Lemma 8 and compute $k_3$ in $O(m_{\tau }^2/\log m_{\tau }+n_{\tau }{\log }^2{m}_{\tau })$ time. As discussed before, it suffices to compute $k_2$, i.e., the number of pairs $(s_r,s_b)$ that satisfy the four conditions in Observation 9. We show below that $k_2$ can be computed in $O(m_{\tau }^2{\log }^2{m}_{\tau }+n_{\tau }{\log }^4{m}_{\tau })$ time. For notational convenience, we let $n=n_{\tau }$ and $m=m_{\tau }$ in this proof.

Let $B$ denote the set of short blue arcs and let $R$ be the set of long red arcs of $S(\tau )$. For each short blue arc $s_b$, define $A(s_b)$ as the common intersection of the wedge $w(s_b)$ and $lun{e}^{\prime }(s_b)$. Note that the underlying disk of a long-red arc $s_r$ does not contain either endpoint of a short-blue arc $s_b$ if and only if the center of $s_r$ is in $lun{e}^{\prime }(s_b)$. Hence, the first two conditions of Observation 9 are satisfied if and only if the center of $s_r$ is in $A(s_b)$.

Recall that centers of all red arcs are in the square cell $C_r$. Let $A^{\prime }(s_b)=A(s_b)\cap C_r$. Note that other than those on $\partial C_r$, $\partial A^{\prime }(s_b)$ consists of at most two line segments and at most two circular arcs; we use general-arcs to refer to these arcs and segments (a segment can be considered as a circular arc of infinite radius). Hence, $\partial A^{\prime }(s_b)$ has at most four general-arcs. We call $A^{\prime }(s_b)$ the interesting region of $s_b$. Let $I$ denote the set of interesting regions of all arcs of $B$. Let $E$ denote the set of general-arcs of all regions of $I$. Hence, $|E|=O(m)$.

We compute a hierarchical $(1/r)$-cutting ${\mathrm{\Xi }}_0,{\mathrm{\Xi }}_1,\mathrm{\dots },{\mathrm{\Xi }}_k$ on the general-arcs of $E$, with $r=m$ and a constant ratio $\rho$ as described in Section 2. This can be done in $O(mr)$ time by Theorem 1. For each cell $\sigma \in {\mathrm{\Xi }}_i$, $1\le i\le k$, we define a canonical pair $(B_{\sigma },R_{\sigma })$, with $B_{\sigma }\subseteq B$ and $R_{\sigma }\subset R$, so that centers of all arcs of $R_{\sigma }$ lie in the interesting region of each short blue arc of $B_{\sigma }$. Specifically, $R_{\sigma }$ consists of all long red arcs whose centers are located in the cell $\sigma$ and $B_{\sigma }$ consists of the arcs of $B$ whose interesting regions contain $\sigma$ but do not contain the parent cell of $\sigma$ in ${\mathrm{\Xi }}_{i-1}$. The canonical pairs of all cells of all cuttings ${\mathrm{\Xi }}_i$, $1\le i\le k$, can be computed in $O(mr+n\log m)$ time, as follows.

For the center $p$ of each long red arc $s_r$, we locate the cell $\sigma$ of ${\mathrm{\Xi }}_i$ containing $p$, for all $1\le i\le k$, and add $s_r$ to $R_{\sigma }$, which can be done in $O(\log r)$ time. As such, computing the canonical sets $R_{\sigma }$ for all cells $\sigma$ takes $O(n\log m)$ time in total. For computing $B_{\sigma }$, we can use an algorithm similar to the one in Lemma 4 (i.e., replacing $lune(s_b)$ by the interesting region $A^{\prime }(s_b)$). More specifically, for each child cell $\sigma \in {\mathrm{\Xi }}_i$ of a cell ${\sigma }^{\prime }$ in ${\mathrm{\Xi }}_{i-1}$, for each general-arc of $E_{{\sigma }^{\prime }}$ (i.e., the set of general-arcs of $E$ crossing ${\sigma }^{\prime }$), suppose it is a general-arc of $A^{\prime }(s_b)$ of a blue arc $s_b$. We check whether $A^{\prime }(s_b)$ contains $\sigma$; if yes, we add $s_b$ to $B_{\sigma }$. In this way, computing all canonical subsets $B_{\sigma }$ takes time proportional to the total size of the subsets $E_{{\sigma }^{\prime }}$ for all cells ${\sigma }^{\prime }$ of all cuttings ${\mathrm{\Xi }}_i$, $i=0,1,\mathrm{\dots },k-1$, which is $O(mr)$.

By the definition of canonical subset pairs $(B_{\sigma },R_{\sigma })$, to compute $k_2$, it suffices to compute the number of pairs of arcs $(s_b,s_r)$ such that $s_b\in B_{\sigma }$, $s_r\in R_{\sigma }$, $\alpha (s_b)$ intersects $\alpha (s_r)$, and the center of $s_b$ is in $w(s_r)$, for all cells $\sigma \in {\mathrm{\Xi }}_i$, $i=1,2,\mathrm{\dots },k$. Below we describe an algorithm of $O(m_{\sigma }^2/\log m+n_{\sigma }\log m)$ time for one such cell $\sigma \in {\mathrm{\Xi }}_i$, where $m_{\sigma }=|B_{\sigma }|$ and $n_{\sigma }=|R_{\sigma }|$.

Recall that all centers of red arcs are in the square cell $C_r$. Define $𝒟$ as the set of disks of radius $2$ centered at the centers of all blue arcs of $B_{\sigma }$. Let $P$ be the set of all centers of the arcs of $R_{\sigma }$; if $p\in P$ is the center of an arc $s_r\in R_{\sigma }$, we use $s(p)$ to refer to $s_r$. It is not difficult to see that the problem is equivalent to computing the number of pairs $(p,D)$, $p\in P$, $D\in 𝒟$, such that $p$ is contained in $D$ and the center of $D$ is in $w(s(p))$. To solve the problem, we use an algorithm similar to that for Lemma 4, with an additional level of range searching data structure for handling the constraint that the center of $D$ is in $w(s(p))$. We briefly discuss it below. Note that $m_{\sigma }=|𝒟|$ and $n_{\sigma }=|P|$.

For each disk $D\in 𝒟$, the intersection of $\partial D$ and $C_r$ consists of at most two circular arcs. Let $H$ denote the set of circular arcs $\partial D\cap C_r$ for all disks $D\in 𝒟$. We build a hierarchical $(1/r^{\prime })$-cutting ${\mathrm{\Xi }}_0^{\prime },{\mathrm{\Xi }}_1^{\prime },\mathrm{\dots },{\mathrm{\Xi }}_{k^{\prime }}^{\prime }$ for $H$, with $r^{\prime }=m_{\sigma }/\log m$ and a constant ratio ${\rho }_1$, in $O(m_{\sigma }{r}^{\prime })$ time [10]. For each cell $\beta \in {\mathrm{\Xi }}_i^{\prime }$, for all $i=1,2,\mathrm{\dots },k$, define $𝒟(\beta )$ as the set of disks of $𝒟$ that contain $\beta$ but do not contain the parent cell of $\beta$ in ${\mathrm{\Xi }}_{i-1}^{\prime }$. We can compute $𝒟(\beta )$ explicitly for all cells of in $O(m_{\sigma }{r}^{\prime })$ time. We further build a range searching data structure on the centers of $𝒟(\beta )$ for answering the following queries: Given a query wedge, compute the number of disk centers in the wedge. For this, we use a data structure of Matoušek’s [14] (i.e., Lemma 6.1 [14] by setting $p=2$), which takes $O({|𝒟(\beta )|}^2/{\log }^{1-\delta }|𝒟(\beta )|)$ preprocessing time for any $\delta >0$ and can answer each query in $O({\log }^2|𝒟(\beta )|)$ time. In addition, for each cell $\beta \in {\mathrm{\Xi }}_{k^{\prime }}^{\prime }$, we explicitly store the subset $H_{\beta }$ of arcs of $H$ crossing $\beta$.

All above can be done in $O(m_{\sigma }{r}^{\prime })$ time except that for building the wedge range searching data structures. We now analyze the total time for constructing these wedge range searching data structures. For each cell $\beta \in {\mathrm{\Xi }}_i$, it holds that $|𝒟(\beta )|=O(m_{\sigma }/{\rho }_1^{i-1})$. Since ${\mathrm{\Xi }}_i$ has $O({\rho }_1^{2i})$ cells, the total time for constructing the data structures is big-O of ${\sum }_{i=1}^{k^{\prime }}{\rho }_1^{2i}\cdot m_{\sigma }^2/{\rho }_1^{2(i-1)}/{\log }^{1-\delta }(m_{\sigma }/{\rho }_1^{i-1})$, which is bounded by $O(m_{\sigma }^2\log m)$ as ${\rho }_1$ is a constant.

For each point $p\in P$, we locate the cell ${\beta }_i$ of ${\mathrm{\Xi }}_i^{\prime }$ containing $p$ for each $i=1,2,\mathrm{\dots },k^{\prime }$; using the wedge range searching data structure on the centers of $𝒟({\beta }_i)$, we find the number $m_{{\beta }_i}$ of centers of disks of $𝒟({\beta }_i)$ contained in the wedge $w(s(p))$. We add all these values $m_{{\beta }_i}$ to a total count $m_p$ (initially, $m_p=0$). Finally, for the cell ${\beta }_k\in {\mathrm{\Xi }}_k^{\prime }$, for each arc $s\in H_{{\beta }_k}$, we check whether the underlying disk of $s$ contains $p$ and the center of $s$ is in $w(s)$; if yes, we increases $m_p$ by one. The value $m_p$ thus obtained is equal to the number of disks $D$ of $𝒟$ that contain $p$ and whose centers are in $w(s(p))$. The time for computing $m_p$ is $O(\log r^{\prime }{\log }^{2}m)$ as $|H_{\beta }|=O(\log m)$ for any cell $\beta \in {\mathrm{\Xi }}_k^{\prime }$. The sum ${\sum }_{p\in P}{m}_p$ is equal to the number of pairs $(p,D)$, $p\in P$, $D\in 𝒟$, such that $p$ is contained in $D$ and the center of $D$ is in $w(s(p))$. As $n_{\sigma }=|P|$, the total time of the algorithm is $O(m_{\sigma }{r}^{\prime }+m_{\sigma }^2\log m+n_{\sigma }\log r^{\prime }{\log }^{2}m))$, which is $O(m_{\sigma }^2\log m+n_{\sigma }{\log }^{3}m)$ for $r^{\prime }=m_{\sigma }/\log m$.