Incidences Between Curves and Points on the Grid

The simplest formulation of the incidence problem involves incidences between points and lines in the plane, where Szemerédi and Trotter [14] showed an upper bound of $O(n^{2/3}{m}^{2/3}+n+m)$, which is tight in the worst case [7] (see also [13, Chapter 1] and [11] for an overview of this and other results).

For more general settings, the work of Sharir and Zahl [12] yields the following best known upper bound for $I(P,\mathrm{\Gamma })$, for arbitrary sets $P$ of $n$ points and $\mathrm{\Gamma }$ of $m$ algebraic curves with $t$ degrees of freedom, that is, the number of real parameters needed to specify a curve of $\mathrm{\Gamma }$. The parameter $t$ is also referred to as the parametric dimension of $\mathrm{\Gamma }$. In this case the bound is

where the $O^{\ast }(\cdot )$ notation hides subpolynomial factors. See also the earlier works [5, 3, 10] for the case of curves with $t=3$, such as circles or parabolas. Combined with the very recent result of Janzer et al. [8], these results yield the following slightly improved bound (with no subpolynomial factors):

An early celebrated work of Bombieri and Pila [6] has studied the case where the points of $P$ form the vertex set of a $\sqrt{n}\times \sqrt{n}$ integer lattice (or grid, as we call it in this work), and each curve in $\mathrm{\Gamma }$ is an irreducible algebraic curve of degree $d$. They have shown, using a fairly involved algebraic analysis, that each such curve $\gamma \in \mathrm{\Gamma }$ contains at most $O^{\ast }(n^{1/(2d)})$ lattice points, leading to an upper bound of $O^{\ast }(m{n}^{1/(2d)})$ on the number of incidences involving $m$ such curves.

The analysis in [6] (as well as the more general case studied in [12] for arbitrary point sets) strongly relies on the algebraic structure of the input curves. If, however, the curves are not necessarily algebraic, but merely have a “well behaved” structure, then the analysis in [6] (and [12]) no longer applies in general. Specifically, we are interested in settings where the only assumptions are that each curve in $\mathrm{\Gamma }$ consists of $O(1)$ strictly convex or concave portions, and each pair of these curves intersect in at most $s$ points, where $s>0$ is a constant integer parameter. In such a case the best bound we are aware of is $O(m{n}^{1/3})$. This bound is mentioned in [13, Chapter 3], and, for the sake of completeness, we present below, in Section 3 (see Proposition 4), a full analysis that derives this bound, in a somewhat more general setup. The $O(m{n}^{1/3})$ bound is somewhat weak, since it does not depend on $s$, and it is also linear in $m$, so it tends to be large when $|\mathrm{\Gamma }|$ is large. Our main goal in this paper is to obtain an improved incidence bound for arbitrary curves that satisfy the assumptions made above, and for points that lie on a square grid (as above), or, more generally, on a rectangular grid (which turns out to be a considerably more challenging problem).

In this work we significantly improve the “default” bound in Proposition 4 for the case where each pair of curves in $\mathrm{\Gamma }$ intersect in at most $s$ points, for some constant integer parameter $s>0$. We also allow the curves in $\mathrm{\Gamma }$ to contain line segments, and therefore weaken the assumption of strict convexity (or concavity). (This extension is essentially trivial, in view of the Szemerédi-Trotter bound [14].) We then obtain, in Section 2, the following bound for the case of a square grid:

In particular, one can easily verify that the bound in Theorem 1 is $O\left(n^{2/3}{m}^{2/3}+m+n\right)$ for pseudo-lines (curves with $s=1$), and $O\left(n^{2/3}{m}^{2/3}+n^{1/2}{m}^{5/6}+m+n\right)$ for pseudo-parabolas or pseudo-circle (curves with $s=2$), under the assumption that each curve can be decomposed into a constant number of convex/concave pieces. We comment that the bound in this theorem is worst-case tight for parabolas, using a construction inspired by Elekes (see, e.g., [13, Chapter 1]), but it requires a rectangular grid, which is the case we study in Section 3. In this latter section we assume that the points of $P$ are the vertices of a $\sqrt{(n/K)}\times \sqrt{nK}$ uniform grid, for some parameter (this parameter is also referred to as the “aspect ratio” of $P$). For this setting, we present a more involved analysis, where we show:

Note that case (i) in Theorem 2 essentially extends the bound in Theorem 1 to “nearly” square grids, whereas case (iii) implies that the bound is similar to the standard one (stated in Proposition 4), if the aspect ratio of the grid is relatively “large”. The logarithmic factors in (i) and (ii) are artifacts of our analysis, and we believe that they can be removed with a more refined analysis.

Our proof technique is mainly combinatorial (i.e., avoids any algebraic considerations, which are irrelevant in our setup), and consists of two major ingredients: (i) A Turán-type bound [9] that is exploited as a black box (see Section 2 for more details), and (ii) a construction inspired by the “curvature-based” approach of Afshani and Cheng [1], who established an upper bound for the cost of semi-algebraic range reporting for planar semi-algebraic regions of constant complexity and points uniformly distributed in the unit square. We adapt, in a nontrivial manner, their machinery to derive incidence bounds for the case of point sets on a uniform grid, as specified in Theorems 1 and 2.

On the algorithmic front, following the analysis in [1], we present a variant of our solution for the square grid setting, for semi-algebraic range searching for points of “bounded spread” and planar semi-algebraic regions of constant complexity. Specifically, the input consists of a set $P$ of $n$ points, and the spread of $P$, defined as ${\max }_{p,q\in P}|pq|/{\min }_{p,q\in P}|pq|$, is $\mathrm{\Theta }(\sqrt{n})$ (which is asymptotically the smallest possible). In particular, this assumption includes the case where each point of $P$ lies close to a distinct grid vertex (of the $\sqrt{n}\times \sqrt{n}$ grid). The goal is to obtain a space-query tradeoff bound for (online) semi-algebraic range reporting for $P$, where the query ranges belong to a family $ℛ$ of semi-algebraic regions of parametric dimension $t$ (recall that $t$ is the number of parameters needed to specify a range in $ℛ$). That is, for each query range, we want to efficiently report all the input points that lie in that range. In Section 4 we adapt the machinery in [1] and show:

The main difference between our setting and the one presented in [1] is that in the latter the points in $P$ are randomly and uniformly drawn in the unit square $U$, which makes the estimation of the expected number of points contained inside an region enclosed within $U$ fairly straightforward. On the other hand, when we only assume that $P$ has a $\mathrm{\Theta }(\sqrt{n})$ spread, this estimation becomes trickier and requires further considerations.

Our analysis uses the following construction inspired by [1]. Let $1\le r\le \sqrt{n}$ be an integer parameter, which we will set later. We partition the unit square $U$ into a uniform $r\times r$ grid $G$. As a result, we obtain a partition of $P$ into $r^2$ subsets, each confined to a grid cell $\tau$ of $G$, which has side length $1/r$ and contains $O(n/r^2)$ points of $P$. (Points on boundaries of cells of $G$ are assigned arbitrarily to one of the neighboring cells, say, to either the lower or the left cell.) We then construct, for each cell $\tau \in G$, a family of canonical slabs, which we will use to cover the portions $\gamma \cap \tau$ of the curves $\gamma \in \mathrm{\Gamma }$ that cross $\tau$. The construction of these slabs proceeds as follows. For $i=0,\mathrm{\dots },\lfloor \log r\rfloor$, fix the parameter ${\alpha }_i=2^i/r$ (which lies in $[0,1]$). We first partition $\tau$ into vertical interior-disjoint slabs of width ${\alpha }_i/r=2^i/r^2$ (and length $1/r$); the number of these slabs is $O(1/{\alpha }_i)=O(r/2^i)$. We then create $\lceil \pi r/2^i\rceil$ rotated copies of the $i$-th partition, so that the $j$-th copy is a rotation of the vertical partition by the angle $2^{i}j/r$. The slabs within each rotated family are extended or shrunk to fit within $\tau$, so their lengths vary between $0$ and $\sqrt{2}/r$. Let ${\mathrm{\Sigma }}_i$ be the collection of these canonical slabs, for a fixed $i$, over all cells $\tau \in G$ (and all rotations). We refer to the slabs in ${\mathrm{\Sigma }}_i$ as slabs of type $i$, or as $i$-slabs for short. We repeat the above construction for each $i=0,\mathrm{\dots },\lfloor \log r\rfloor$, and denote by $\mathrm{\Sigma }$ the union ${\bigcup }_i{\mathrm{\Sigma }}_i$. Put $L_i=|{\mathrm{\Sigma }}_i|$. By the above construction, $L_i$ is the number of grid cells, which is $r^2$, times the number of $i$-slabs in a cell, which is $O((r/2^i)\cdot (1/{\alpha }_i))=O(r^2/2^{2i})$; that is, we have $L_i=O(r^4/2^{2i})$.

Within each slab $\sigma \in \mathrm{\Sigma }$ we bound the number of incidences between the points of $P\cap \sigma$ and a certain subfamily of the curves $\gamma \in \mathrm{\Gamma }$ that intersect $\sigma$ (see below for the precise definition). In order to do so, we need (i) to estimate $|P\cap \sigma |$, and (ii) to construct, for each $\gamma \in \mathrm{\Gamma }$, a small-sized set of slabs in $\mathrm{\Sigma }$ that cover $\gamma$. Each slab $\sigma$ interacts with all the curves that use $\sigma$ for their cover – see below.

Beginning with task (i), we apply Pick’s theorem (see [4]), which measures the area of a nondegenerate simple polygon $Q$ with vertices on the unit grid, in terms of the number of grid points that it contains. Specifically, let $\mu (Q)$ be the area of $Q$, let $I$ (resp., $B$) be the number of points of $P$ in the interior (resp., on the boundary) of $Q$. Then Pick’s theorem asserts that $\mu (Q)=I+B/2-1$. In our case, each coordinate is shrunk by $\sqrt{n}$, so, for a nondegenerate simple polygon $Q$ with vertices on $P$ (which is the shrunk $\sqrt{n}\times \sqrt{n}$ grid), we have $n\mu (Q)=I+B/2-1$, implying that

Let $\sigma \in \mathrm{\Sigma }$ be a canonical $i$-slab. Replace $\sigma$ by the convex hull $C(\sigma )\subseteq \sigma$ of $P\cap \sigma$. ²²2We apply this replacement since the vertices of $\sigma$ do not necessarily belong to $P$, and this property is necessary in order to apply Pick’s theorem. Then

The additive term $2$ is subsumed in this bound as long as $r$ is not too large and $i$ is not too small. When the bound $O\left(2^{i}n/r^3\right)$ is smaller than $1$, we get $|P\cap \sigma |=O(1)$. Nevertheless, in this case too we will use the bound $O(2^{i}n/r^3)$, with some care, and explain later why this does not cause any problems. We also note that this bound holds as long as $P\cap \sigma$ is not a collinear set of points (which is the case when $\mu (C(\sigma ))=0$). Degenerate situations of this kind will be handled separately, in a rather simple manner – see below.

For task (ii), we follow a variant of the analysis in [1]. Let $\gamma$ be a curve in $\mathrm{\Gamma }$. We may assume that $\gamma$ is (strictly) convex or (strictly) concave, and is both $x$-monotone and $y$-monotone; otherwise, by property (iii) we can partition $\gamma$ into $O(1)$ pieces of this kind. The turning angle $\theta ({\gamma }^{\prime })$ of a connected portion ${\gamma }^{\prime }$ of $\gamma$ is the difference $|{\theta }_2-{\theta }_1|$ between the orientations ${\theta }_1$, ${\theta }_2$ of the tangents to ${\gamma }^{\prime }$ at its endpoints. Because of convexity, the tangent orientations always increase or always decrease along ${\gamma }^{\prime }$, so the orientation of every tangent to ${\gamma }^{\prime }$, as well as that of the chord connecting the endpoints of ${\gamma }^{\prime }$, lies between ${\theta }_1$ and ${\theta }_2$. See Figure 1.

Now let $\tau$ be a cell of $G$ that $\gamma$ crosses. By our assumptions, the intersection ${\gamma }^{\prime }=\gamma \cap \tau$ is a single connected component of $\gamma$. Let ${\theta }^{\prime }$ denote the turning angle of ${\gamma }^{\prime }$. As is easily checked, ${\gamma }^{\prime }$ can be enclosed in a (not necessarily canonical) slab ${\sigma }^{\prime }$ of width $c{\theta }^{\prime }/r$, for some absolute constant $c$. Let $i$ be the index such that . When we still use the index $0$ (see below), and we may assume that ${\theta }^{\prime }\le 1$; otherwise break ${\gamma }^{\prime }$ further into $O(1)$ pieces that satisfy this property.

Then, as is easily checked, ${\sigma }^{\prime }$ can be enclosed in the union of $O(1)$ canonical $i$-slabs. See also [1, Lemma 30] for a similar property. This is illustrated in Figure 2. (Note that ${\gamma }^{\prime }$ might end inside a cell, but this does not harm the analysis.)

Fix an index $i$, and let ${\mathrm{\Gamma }}_i$ denote the collection of all the arcs ${\gamma }^{\prime }=\gamma \cap \tau$, over the curves $\gamma \in \mathrm{\Gamma }$ and the cells $\tau$ of $G$, for which . Since each piece in ${\mathrm{\Gamma }}_i$ consumes at least $2^{i-1}/r$ of the turning angle of the containing curve $\gamma$, the number of pieces of $\gamma$ in ${\mathrm{\Gamma }}_i$ is at most $O(r/2^i)$. For pieces ${\gamma }^{\prime }$ with (which are left out of the preceding analysis), the $x$-monotonicity itself implies that $\gamma$ crosses at most $O(r)$ cells of $G$, allowing us to extend the first range to $[0,1/r)$. That is, we have shown that each curve $\gamma \in \mathrm{\Gamma }$ contributes $O(r/2^i)$ pieces to ${\mathrm{\Gamma }}_i$, and each such piece can be covered by $O(1)$ (canonical) $i$-slabs.

Fix an $i$-slab $\sigma$, let $P(\sigma )=P\cap \sigma$, and ${\mathrm{\Gamma }}_i(\sigma )$ be the set of the portions within $\sigma$ of the curves of $\mathrm{\Gamma }$ that use $\sigma$ in their cover (so their turning angles within the cell of $G$ that contains $\sigma$ lie in $[2^{i-1}/r,2^i/r)$, or in $[0,1/r)$ for $i=0$). As shown earlier, assuming $P(\sigma )$ is not collinear,

Put $m_{\sigma }=|{\mathrm{\Gamma }}_i(\sigma )|$, and observe that, summing over all $i$-slabs,

(This is because each covering slab “consumes” $\mathrm{\Omega }(2^i/r)$ of the turning angle of the curve.) We now apply an incidence bound to $P(\sigma )$ and ${\mathrm{\Gamma }}_i(\sigma )$, using the following considerations. Assume first that $P(\sigma )$ is not collinear. In such a case, we apply a moderate incidence bound using a Turán-type bound. Specifically, since each pair of curves in $\mathrm{\Gamma }$ intersect in at most $s$ points, it follows that the incidence graph of $P(\sigma )$ and ${\mathrm{\Gamma }}_i(\sigma )$ (and, in general, also the incidence graph of $P$ and $\mathrm{\Gamma }$) does not contain any copy of $K_{s+1,2}$. Therefore, by a result of Kövari, Sós and Turán [9], it follows that

where the left-hand side is the number of edges in this incidence graph. In what follows, and unless stated otherwise, we will mostly be using the bound in (5).

If $P(\sigma )$ is collinear then, since we have assumed that $\mathrm{\Gamma }$ does not contain any line segments, each arc of ${\mathrm{\Gamma }}_i(\sigma )$ can have at most two incidences with $P(\sigma )$ (since each such arc is strictly convex/concave, it must intersect any line in at most two points), for a total of at most $2m_{\sigma }$ incidences, which is subsumed in the above bound. In addition, if the bound in (3) on $n_{\sigma }$ is smaller than $1$, the actual value of $n_{\sigma }$ is $O(1)$, in which case

which is again subsumed in the above bound. Hence there is no harm if we use (with some care – see below) the bound in (3), even when it is smaller than $1$. Letting ${\mathrm{\Gamma }}_i$ denote the collection ${\bigcup }_{\sigma \in {\mathrm{\Sigma }}_i}{\mathrm{\Gamma }}_i(\sigma )$, and summing this bound over all $i$-slabs $\sigma$, we thus obtain

where $n_{\sigma ,\max }$ is the upper bound in (3). The following calculations handle slabs $\sigma$ for which this bound is $\ge 1$. Slabs for which this bound is smaller than $1$ are handled in a much simpler manner – see below. Next, using Hölder’s inequality, we obtain

Recall that we have ${\sum }_{\sigma \in {\mathrm{\Sigma }}_i}{m}_{\sigma }=O(mr/2^i)$, $n_{\sigma ,\max }=O(2^{i}n/r^3)$ (where we assume for now that this bound is $\ge 1$), and $L_i=O(r^4/2^{2i})$. Substituting these bounds in the above inequality, we obtain:

We sum these bounds over the $O(\log r)$ values of $i$ for which $2^i\ge r^3/n$ (i.e., $n_{\sigma ,\max }\ge 1$). Since $i$ appears only in the denominators, we obtain decreasing geometric sums, which we can bound by their leading terms. We therefore obtain the incidence bound $O\left({\displaystyle \frac{n{m}^{1-1/(s+1)}}{r^{2-3/(s+1)}}}+mr\right)$.

For $i$ satisfying (note that there is no such $i$ when $r\le n^{1/3}$), the bound per slab is, as argued above, just $O(m_{\sigma })$, and the sum of these bounds is just $O(mr/2^i)$, which, when summed over $i$, is just $O(mr)$. That is, we have $I(P,\mathrm{\Gamma })=O\left({\displaystyle \frac{n{m}^{1-1/(s+1)}}{r^{2-3/(s+1)}}}+mr\right)$.

We balance these terms by choosing

For this choice to make sense, we need to require that $1\le r\le n^{1/2}$. When $r$ (in the above expression) is smaller than $1$, we replace it by $1$, and when $r>n^{1/2}$, we replace it by $n^{1/2}$. In the former case the first term decreases and the second term increases (and thus dominates the first term), so the bound becomes $O(m)$. In the latter case we have the relation $r>n^{1/2}$, which implies that $n^{s+1}/m>n^{3s/2}$, which is easily seen to be impossible for any $s\ge 2$ (unless $m$ and $n$ are constants). When $s=1$ (the case of pseudo-lines), this inequality implies that $m$ is at most $O(\sqrt{n})$. In this particular case, we apply the bound in (6) on the number of incidences, from which we obtain $I(P,\mathrm{\Gamma })=O\left(m{n}^{1/2}+n\right)=O(n)$. We have thus shown:

Recall our discussion earlier in this section, where we also consider the case where property (i) does not hold for $\mathrm{\Gamma }$, and, as a result, need to add $O(n^{2/3}{m}^{2/3}+n+m)$ to the bound. (When no line segments are allowed, we only get the bound in (9).) This completes the proof of Theorem 1.

Let $P$ be the set of $n$ vertices of a uniform grid drawn within the rectangle $R=[0,1]\times [0,K]$, for some integer (which may depend on $n$), and assume, without loss of generality, that $\sqrt{n/K}$ is an integer. We now construct a $\sqrt{n/K}\times \sqrt{nK}$ uniform grid within $R$, so each of its cells is a square of side length $\sqrt{K/n}$. Let $\mathrm{\Gamma }$ be a set of $m$ curves satisfying properties (i)–(iii) of Section 2.

In this section we extend the analysis in the preceding section, to derive an improved upper bound on $I(P,\mathrm{\Gamma })$. Somewhat surprisingly, the analysis gets considerably more complicated in this case.

We begin with the following well-known property (see, e.g., [13]). For the sake of completeness, we present a proof that also holds for rectangular grids.

1. (a)

   Assume that the grid is a $k\times \mathrm{\ell }$ grid, with $k\mathrm{\ell }=n$. Without loss of generality, we may assume that the given curve $\gamma$ is strictly convex and is both $x$- and $y$-monotone, and replace it by the polygonal convex curve ${\gamma }_1$ that connects the grid points on $\gamma$ in a left-to-right order. An edge of ${\gamma }_1$ may contain many grid points, but we only consider the two extreme ones, because, by assumption, none of the interior points lies on $\gamma$. The vector along each edge of ${\gamma }_1$ is of the form $(\mathrm{\Delta }x,\mathrm{\Delta }y)$, where $\mathrm{\Delta }x\in [1,k-1]$ and $\mathrm{\Delta }y\in [1,\mathrm{\ell }-1]$. Fix two parameters $u$, $v$, whose values will be set later. An edge $e$ of ${\gamma }_1$ is long if either $\mathrm{\Delta }x\ge u$ or $\mathrm{\Delta }y\ge v$, and short otherwise. Since each long edge advances by at least $u$ columns to the right, or by at least $v$ rows upwards, the number of long edges is at most $\frac{k}{u}+\frac{\mathrm{\ell }}{v}$. For short edges, their slopes are of the form $\frac{\mathrm{\Delta }y}{\mathrm{\Delta }x}$, for $\mathrm{\Delta }x\in [1,u-1]$, $\mathrm{\Delta }y\in [1,v-1]$. The number of such slopes is at most $uv$, and because $\gamma$ is strictly convex, the slopes of its edges are all distinct, implying that the number of short edges is at most $uv$.

   We now set $u$ and $v$ to satisfy ${\displaystyle \frac{k}{u}}={\displaystyle \frac{\mathrm{\ell }}{v}}=uv$. The solution of these equations is $u={\displaystyle \frac{k^{2/3}}{{\mathrm{\ell }}^{1/3}}}$ and $v={\displaystyle \frac{{\mathrm{\ell }}^{2/3}}{k^{1/3}}}$. Hence the number of grid points on $\gamma$ is $O(uv)=O\left(k^{1/3}{\mathrm{\ell }}^{1/3}\right)=O\left(n^{1/3}\right)$.

   Note that this analysis holds when $k\ge \sqrt{\mathrm{\ell }}$ and $\mathrm{\ell }\ge \sqrt{k}$. When, say, , the claim is trivial, as the grid has at most $n^{1/3}$ columns. A symmetric argument applies when . If $\gamma$ consists of $O(1)$ strictly convex or concave pieces, we apply the preceding analysis to each piece separately. This completes the proof of (a).

2. (b)

   The parabola $y=x^2$ passes through $n^{1/3}$ vertices of the $n^{1/3}\times n^{2/3}$ grid.

$◀$

We use the following modification of the earlier construction. While several parts of the analysis are similar, there are quite a few additional or different details that need to be worked out, to justify some overlap in the presentations. Let $1\le r\le \sqrt{n/K}$ be an integer parameter, which we will set later.³³3We will actually be using several different values of $r$; see below. We partition $R$ into an $r\times rK$ uniform grid $G$, which yields a partition of $P$ into $r^{2}K$ subsets, each confined to a grid cell $\tau$ of $G$, each of which has side length $1/r$ and contains $O(n/(r^{2}K))$ points of $P$. As in Section 2, we then construct, for each cell $\tau \in G$, a family of canonical slabs, which we will use to cover the portions $\gamma \cap \tau$ of the curves $\gamma \in \mathrm{\Gamma }$ that cross $\tau$. The slabs are now of two kinds. The first family of slabs, which we refer to as ${\mathrm{\Sigma }}^{(1)}$, is similar to the one constructed earlier for square grids, but with some nontrivial modifications (see below for details). The second family, denoted by ${\mathrm{\Sigma }}^{(2)}$ (see below for the definition) is of a new, narrower kind of slabs, and most of this section analyzes the structural behavior of these slabs, and presents several combinatorial properties that we exploit in order to bound the number of incidences that these slabs contribute. Having these properties, the actual derivation of the incidence bound is mainly technical. The analysis for ${\mathrm{\Sigma }}^{(1)}$ is similar, but simpler; see below.

Generally speaking, the main difference between the setup here and the previous setup is that curves can cross a potentially larger number of cells of $G$, up to $\mathrm{\Theta }(rK)$ of them, and this amount can potentially increase the incidence bound if we only use slabs of ${\mathrm{\Sigma }}^{(1)}$ (informally, these slabs are too wide for this setup). To address this issue, we apply two main modifications: (i) We partition the curves in $\mathrm{\Gamma }$ into subarcs, depending on their “steepness” (see below), and bound the number of incidences with respect to each of these portions separately. (ii) We use a second family, namely ${\mathrm{\Sigma }}^{(2)}$, of narrower slabs, which were not needed in the case of a square grid. We first introduce the structure of these curves and of the narrower slabs, and discuss the interaction between them, and then present the analysis for the total incidence bound.

Consider a curve $\gamma \in \mathrm{\Gamma }$ that crosses $tr$ cells of $G$, for some $t>2$; note that no such curves arose in the case of square grids (after having split each of them into monotone (strictly) convex/concave pieces). As in Section 2, we may assume that $\gamma$ is (strictly) convex or concave and is both $x$-monotone and $y$-monotone; any curve in our family can be partitioned into $O(1)$ such curves. For concreteness, assume that $\gamma$ is concave (i.e., its tangents turn clockwise as we go up), and is the graph of an increasing function; all the other cases, where $\gamma$ is convex and/or decreasing, are treated in a fully symmetric manner. Now let $\tau$ be a cell of $G$ that $\gamma$ crosses. The intersection ${\gamma }^{\prime }=\gamma \cap \tau$ is connected. We assign to ${\gamma }^{\prime }$ the orientations , with respect to the $y$-axis, of the tangents to ${\gamma }^{\prime }$ at its bottom and top endpoints, respectively, and put $\mathrm{\Delta }\theta ({\gamma }^{\prime })={\theta }_2({\gamma }^{\prime })-{\theta }_1({\gamma }^{\prime })>0$.

The orientation of the chord that connects the endpoints of ${\gamma }^{\prime }$, as well as the orientations of all the tangents to ${\gamma }^{\prime }$, lie between ${\theta }_1({\gamma }^{\prime })$ and ${\theta }_2({\gamma }^{\prime })$. We define the steepness of ${\gamma }^{\prime }$ as the (larger) orientation ${\theta }_2({\gamma }^{\prime })$, and its flatness as $\mathrm{\Delta }\theta ({\gamma }^{\prime })$. Comparing to the analysis in Section 2, the flatness of a curve represents its turning angle (although we now consider much smaller values than those used in Section 2). The steepness is a new measure (that was not needed for the analysis in Section 2), whose role is to control the number of cells of $G$ crossed by a curve (i.e., a subcurve with a given steepness).

We call ${\gamma }^{\prime }$ a $(q,j)$-arc if its steepness ${\theta }_2({\gamma }^{\prime })$ lies in $[1/2^j,1/2^{j-1})$ and its flatness lies in $[1/(2^{q}r),1/(2^{q-1}r))$, for suitable integer indices $q$ and $j$. Only the case $q\ge 1$ is relevant; less flat curves can be handled by the wider slabs of ${\mathrm{\Sigma }}^{(1)}$, and we treat them separately – see below. We assume that $j\le \log K$, ignoring steeper arcs (because steeper arcs do not cross more cells, namely more than $O(rK)$ cells). The flatness parameter $q$, as just defined, determines the minimum width of a slab that can enclose ${\gamma }^{\prime }$, but nothing prevents us from using wider slabs, i.e., decrease the value of $q$. To emphasize the role of the minimum width, we denote the parameter $q$ just defined as $q^{\ast }$ (an intrinsic parameter of the arc), and refer to it as the true flatness parameter of the arc. See Figure 3 for an illustration.

We extend the notions of steepness and flatness to larger portions of the original curve $\gamma$. Concretely, assume, as above and with no loss of generality, that $\gamma$ is concave and monotone increasing. Let be the tangent orientations of $\gamma$ (with respect to the $y$-axis) at its bottom and top endpoints, respectively. Let $j^{-}\ge j^{+}$ be the integers for which and . We then partition $\gamma$ into arcs ${\gamma }_{j^{+}},{\gamma }_{j^{+}+1},\mathrm{\dots },{\gamma }_{j^{-}}$, so that the tangent orientations of each ${\gamma }_j$ lie in $[1/2^{j+1},1/2^j)$, and refer to ${\gamma }_j$ as a (maximal) $j$-steep subarc (or portion) of $\gamma$. The flatness of ${\gamma }_j$ is the sum of the flatness of its subarcs of intersections with the grid cells of $G$ that it crosses. The definition of steepness is easily seen to imply that ${\gamma }_j$ crosses $O(2^{j}r)$ cells of $G$. Indeed, if we consider the chord $\mathrm{\ell }$ connecting the bottom and top endpoints of ${\gamma }_j$, we obtain a line segment whose slope (with respect to the $y$-axis) lies in $[1/2^{j+1},1/2^j)$, so the $y$-coordinate of the difference between the endpoints of ${\gamma }_j$ is at most $O(2^j)$, and dividing by $1/r$ we get the asserted bound on the number of cells.

We now form⁴⁴4For simplicity, and with no real effect on the analysis, we ignore here rounding issues. $O(\log K)$ families ${\mathrm{\Gamma }}_0,\mathrm{\dots },{\mathrm{\Gamma }}_{\log K}$, where ${\mathrm{\Gamma }}_j$ consists of all maximal $j$-steep portions of curves from $\mathrm{\Gamma }$, for $j=0,\mathrm{\dots },\log K$.⁵⁵5Note that this is slightly abusing the notation of ${\mathrm{\Gamma }}_i$ from Section 2, which has a different meaning. We slightly modify the definition of the first and last families ${\mathrm{\Gamma }}_0$, ${\mathrm{\Gamma }}_{\log K}$, so that ${\mathrm{\Gamma }}_0$ consists of all $j$-steep portions whose tangent orientations lie in the range $[1,\mathrm{\infty })$, and for ${\mathrm{\Gamma }}_{\log K}$ this range is $[0,1/K)$. As will follow, this modification does not harm our analysis. An important property of this partition is that the subfamilies ${\mathrm{\Gamma }}_j$ are independent of $r$, which will be crucial for the forthcoming analysis. In what follows, we bound the number of incidences with respect to each family ${\mathrm{\Gamma }}_j$ separately, and then sum up these bounds over all such families. We comment that the bounds that we will obtain will depend on $r$, and optimizing each of them will require a different choice of $r$. Handling this multitude of values of $r$ requires some careful treatment; see below.

Fix an index $j=0,\mathrm{\dots },\log K$, and consider a maximal $j$-steep subarc $\gamma \in {\mathrm{\Gamma }}_j$. Let $\tau$ be a cell that $\gamma$ crosses. Clearly, the intersection ${\gamma }^{\prime }=\gamma \cap \tau$ is also $j$-steep (it may be even steeper). Let $\mathrm{\Delta }\theta ({\gamma }^{\prime })$ be the turning angle (flatness) of ${\gamma }^{\prime }$. Again refer to Figure 3. If $\mathrm{\Delta }\theta ({\gamma }^{\prime })\ge 1/r$ we can (that is, should) use slabs from ${\mathrm{\Sigma }}^{(1)}$ to cover ${\gamma }^{\prime }$. Assume then that , and let $q^{\ast }\ge 0$ be the integer for which (so ${\gamma }^{\prime }$ is a $(q^{\ast },j)$-arc). Then we can cover ${\gamma }^{\prime }$ by a (non-canonical) slab $\sigma$ of width at least $\mathrm{\Delta }\theta ({\gamma }^{\prime })/r=O(1/(2^{q^{\ast }}{r}^2))$ (see once again Figure 3). Note that we can use wider slabs to cover ${\gamma }^{\prime }$ (the actual width will be determined in the forthcoming analysis).⁶⁶6There is a tradeoff in using wider slabs: their number is smaller but each of them contains more points. The analysis below will address this issue. Let $q$ be the integer parameter for the actual slab that we want to use (so its width is $\mathrm{\Theta }(1/(2^q{r}^2))$, where $q\le q^{\ast }$). To cover $\sigma$ by $O(1)$ canonical slabs of this width, we need to use slabs rotated by multiples of the angle $1/(2^{q}r)$. But since $\gamma$ is $j$-steep in $\tau$, the orientations that we need to use (with respect to the $y$-axis) span an angular range of at most $O(1/2^j)$, so the total number of rotations is $O((1/2^j)/(1/(2^{q}r)))=O(2^{q-j}r)$. For each canonical orientation, the number of slabs at that orientation (within the current cell) is proportional to $1/r$ divided by the width, so it is $O(2^{q}r)$, for a total of $O(2^{2q-j}{r}^2)$ $(q,j)$-slabs, as we call them, in a cell, i.e., a total number of

$(q,j)$-slabs. We also refer to these slabs as $q$-slabs, when $j$ is not important (not to be confused with $i$-slabs of ${\mathrm{\Sigma }}^{(1)}$; see below and Section 2). We denote the family of these slabs as ${\mathrm{\Sigma }}_{q,j}^{(2)}$, and denote their union, over all $q$, as ${\mathrm{\Sigma }}_j^{(2)}$, and over all $q$ and $j$, as ${\mathrm{\Sigma }}^{(2)}$. We let $\mathrm{\Sigma }={\mathrm{\Sigma }}^{(1)}\cup {\mathrm{\Sigma }}^{(2)}$ denote the overall family of slabs.

For technical reasons, we do not want to use too large a value for $q$ (i.e., slabs that are too thin). Our actual choice is (recall that we must have $q\le q^{\ast }$)

Given a $j$-steep (portion of a) curve $\gamma \in {\mathrm{\Gamma }}_j$, the number of cells $\tau$ from $G$ that it crosses is $O(2^{j}r)$, as argued above. Alternatively, each $(q^{\ast },j)$-arc consumes $\mathrm{\Theta }(1/(2^{q^{\ast }}r))$ of the turning angle (flatness) of $\gamma$, so $\gamma$ crosses at most $O((1/2^j)/(1/(2^{q^{\ast }}r)))=O(2^{q^{\ast }-j}r)$ cells of $G$ (in which it behaves as a $(q^{\ast },j)$-arc). Note that in this argument we have to use the true flatness parameter $q^{\ast }$. Hence the overall number of curve-slab interactions of this kind (that involve $(q,j)$-slabs and $(q^{\ast },j)$-arcs) is

where $m_{\sigma }$ is the number of $(q^{\ast },j)$-arcs that use $\sigma$ for their cover. See Figure 4.

As before, within each slab $\sigma \in {\mathrm{\Sigma }}^{(2)}$ we bound the number of incidences between the points of $P\cap \sigma$ and the subfamily of the $j$-steep curves $\gamma \in {\mathrm{\Gamma }}_j$ (for each $j$ separately) that use $\sigma$ for the cover of their portion within the cell of $\sigma$. In order to do so, we need, as before, (i) to estimate $|P\cap \sigma |$, and (ii) to construct, for each $\gamma \in {\mathrm{\Gamma }}_j$, a small-sized set ${\mathrm{\Sigma }}^{(2)}(\gamma )$ of (canonical) slabs in ${\mathrm{\Sigma }}^{(2)}$ that cover $\gamma$. Slabs in ${\mathrm{\Sigma }}^{(1)}$ are handled in a simpler manner, similar to Section 2; see below. Task (ii) has already been addressed, so we mostly consider task (i), and briefly summarize (ii) afterwards.

We apply Pick’s theorem, as in Section 2, which now implies that, for a nondegenerate polygonal region $Q$ whose vertices are grid points⁷⁷7Here the scaling of the area is, as it should be, by $n/K$. $\frac{n}{K}\cdot \mu (Q)=I+B/2-1$, so, as long as $P\cap Q$ is not a collinear set of points,

1. (i)

   Let $\sigma \in {\mathrm{\Sigma }}^{(1)}$ be a canonical $i$-slab. Replace $\sigma$ by the convex hull $C(\sigma )\subseteq \sigma$ of $P\cap \sigma$. We then have

   $$|P\cap \sigma |=|P\cap C(\sigma )|\le \frac{2n}{K}\mu (C(\sigma ))+2\le \frac{2n}{K}\mu (\sigma )+2=O\left(\frac{n{\alpha }_i}{r^{2}K}\right)=O\left(\frac{2^{i}n}{r^{3}K}\right).$$

   (13)

2. (ii)

   For a $(q,j)$-slab $\sigma \in {\mathrm{\Sigma }}^{(2)}$, the same reasoning gives

   $$|P\cap \sigma |=O\left(\frac{n}{K}\cdot \frac{1}{2^q{r}^3}\right)=O\left(\frac{n}{2^q{r}^{3}K}\right).$$

   (14)

Again, here $q$ refers (naturally) to the thickness of the actual slab and not to the true flatness parameter $q^{\ast }$ of any arc that uses the slab for its cover. These bounds hold as long as $P\cap \sigma$ is not collinear, and provided that they are at least $1$. Degenerate situations, when one of these assumptions does not hold, are handled as in Section 2. That is, if $P\cap \sigma$ is collinear then $\sigma$ contributes at most $2m_{\sigma }$ incidences, and the term $O(m_{\sigma })$ in our bound takes care of this case too. Similarly, as in Section 2, when the bound on $|P\cap \sigma |$ in (13) or (14) is smaller than $1$, we take the bound to be $O(1)$ instead. This does not violate the analysis (although some care is needed), as the bound that we derive subsumes the incident count in these cases – see below.

For task (ii), we just summarize the preceding analysis, which shows that the number of cells $\tau$ for which $\gamma$ is $j$-steep and $q^{\ast }$-flat is $O(\min \{2^j,2^{q^{\ast }-j}\}r)$. Hence, the overall number of curve-slab interactions, for $(q,j)$-slabs in ${\mathrm{\Sigma }}_j^{(2)}$ and $(q^{\ast },j)$-arcs, for $q\le q^{\ast }$, is $O(\min \{2^j,2^{q^{\ast }-j}\}mr)$.

The analysis involving slabs of ${\mathrm{\Sigma }}^{(1)}$ is similar to that in Section 2, although some steps of the analysis need to be adjusted to the rectangular setup. Here the width of a slab is associated with the index $i$ (used in Section 2), which replaces the index $q$ used above. The analysis that we present below is a refinement of the analysis in Section 2, where we consider the interaction of $i$-slabs with $j$-steep curves. This refinement was not needed in Section 2, but is needed here due to the fact that a curve $\gamma \in \mathrm{\Gamma }$ may cross $\gg r$ cells of $G$, as mentioned above.

Let $\gamma \in {\mathrm{\Gamma }}_j$ be a maximal $j$-steep curve, and let ${\gamma }^{\prime }=\gamma \cap \tau$. We assume $\mathrm{\Delta }\theta ({\gamma }^{\prime })\ge 1/r$ (otherwise we use slabs of ${\mathrm{\Sigma }}^{(2)}$ to cover $\gamma$), and let $i\ge 0$ be the integer for which . Analogously to the notation and definitions used above, we say that ${\gamma }^{\prime }$ is an $(i,j)$-arc. Then we can cover ${\gamma }^{\prime }$ by a (non-canonical) slab $\sigma$ of width at least $\mathrm{\Delta }\theta ({\gamma }^{\prime })/r=O(2^i/r^2)$. As above, we can cover $\sigma$ by $O(1)$ canonical slabs of this width, which are rotated by multiples of the angle $2^{i-1}/r$. But since $\gamma$ is $j$-steep in $\tau$, the orientations that we actually use (with respect to the $y$-axis) span an angular range of at most $O(1/2^j)$, so the total number of rotations in this case is $O((1/2^j)/(2^i/r))=O(r/2^{i+j})$. For each canonical orientation, the number of slabs at that orientation (within the current cell) is proportional to $1/r$ divided by the width, so it is $O(r/2^i)$, for a total of $O(r^2/2^{2i+j})$ $(i,j)$-slabs in a cell (this is a refinement of the definition of $i$-slabs from Section 2), i.e., a total number of

$(i,j)$-slabs. We denote the family of these slabs as ${\mathrm{\Sigma }}_{i,j}^{(1)}$, and denote their union, over all $i$, as ${\mathrm{\Sigma }}_j^{(1)}$, and over all $i$ and $j$, as ${\mathrm{\Sigma }}^{(1)}$.

Fix an $(i,j)$-slab $\sigma$, let $P(\sigma )=P\cap \sigma$, and ${\mathrm{\Gamma }}_{i,j}(\sigma )$ be the set of curves of ${\mathrm{\Gamma }}_j$ that use $\sigma$ in their cover (so their turning angles within the cell of $G$ that contains $\sigma$ lie in $[2^{i-1}/r,2^i/r)$). Let ${\mathrm{\Gamma }}_{i,j}$ denote the collection, over all $j$-steep curves $\gamma \in {\mathrm{\Gamma }}_j$ and $(i,j)$-slabs $\sigma$, of the portions $\gamma \cap \sigma$ that use $\sigma$ for their cover. That is, ${\mathrm{\Gamma }}_{i,j}={\bigcup }_{\sigma \in {\mathrm{\Sigma }}_{i,j}^{(1)}}{\mathrm{\Gamma }}_{i,j}(\sigma )$. As shown earlier, when $P\cap \sigma$ is nondegenerate, we have in general

the cases where either $P\cap \sigma$ is collinear, or where the bound in (16) is smaller than $1$, are handled as before, namely the incidence bound is $O(m_{\sigma })$ in both cases, where $m_{\sigma }=|{\mathrm{\Gamma }}_{i,j}(\sigma )|$. We next bound, for a $j$-steep curve $\gamma \in {\mathrm{\Gamma }}_j$, the number of cells $\tau$ that it crosses. Each $(i,j)$-arc of $\gamma$ consumes $\mathrm{\Theta }(2^i/r)$ of the turning angle (flatness) of $\gamma$, and since $\gamma$ is $j$-steep it crosses at most $O((1/2^j)/(2^i/r))=O(r/2^{i+j})$ cells of $G$, in which it behaves as an $(i,j)$-arc. Hence the overall number of curve-slab interactions that involve $(i,j)$-slabs and $(i,j)$-arcs is⁸⁸8Here there is no need to use wider slabs, as in the case of ${\mathrm{\Sigma }}^{(2)}$.

We now apply the incidence bound (5) to $P(\sigma )$ and ${\mathrm{\Gamma }}_{i,j}(\sigma )$, and obtain