The second-partitioning-polynomial technique (part 2)

In the previous post we presented the second partitioning polynomial theorem. In this post we give an example of how to apply this theorem. After going over this example, it will be easier to discuss why so far this technique had been used only in {\mathbb R}^3  .

Let \cal P  be a set of m  points and let \Pi  be a set of n  planes, both in {\mathbb R}^3  . Consider a line \ell  such that all the points of \cal P  lie on \ell  and all the planes of \Pi  fully contain \ell  , as in the following figure.

PlaneCommonLine

In this case we have I({\cal P},\Pi)=\Theta(mn)  , which makes the problem not interesting. There exist several definitions of non-degenerate point-plane configurations, which make the problem of bounding the number of incidences more challenging (e.g., see this paper by Elekes and Toth; these non-degenerate configurations are not defined just for the sake of “making the problem less trivial”, and already have various applications). Since we are only interested in presenting the two partitioning polynomials technique, we consider the somewhat simple case where no three planes of \Pi  contain a common line. This problem was already studied over 20 years ago by Edelsbrunner, Guibas, and Sharir, where partitioning of the space by cuttings has led to the bound I({\cal P},\Pi)=O(n^{3/5}m^{4/5} + m\log n)  (they study the dual setting where no three points are collinear, though it is equivalent to our setting). A more general case is studied in a yet unpublished manuscript by Abdul Basit and myself, where the assumption is that no line is contained in k  planes (and k  can also depend on n  ). To further simplify our scenario, we also assume that m=n  .

Theorem 1. Let \cal P  be a set of n  points and let \Pi  be a set of n  planes, both in {\mathbb R}^3  , such that no line is fully contained in three planes of \Pi  . Then I({\cal P},\Pi)=O(n^{7/5})  .

Proof.     We begin just as in the two-dimensional proof that was presented in this post. According to the assumption, any pair of points of \cal P  can be contained in at most two planes of \Pi  (or, recalling the notation that we used in the two dimensional case, the point-plane incidence graph does not contain a copy of K_{2,3}  ). Thus, the Kővári–Sós–Turán theorem implies

I({\cal P},\Pi)=O(|{\cal P}|\sqrt{|\Pi|}+|\Pi|). \ \ \ \ \ (1)

To partition the plane into cells, we construct an n^{3/5}  -partitioning polynomial f  for \cal P  . According to the polynomial partitioning theorem, the degree of f  is O(n^{1/5})  and every cell in {\mathbb R}^2\setminus Z(f)  is an open set that contains at most n/n^{3/5} = n^{2/5}  points of \cal P  . Let t  denote the number of cells in (i.e., connected components of) {\mathbb R}^3\setminus Z(f)  .

We denote by {\cal P}_0 = Z(f) \cap {\cal P}  the set of points of \cal P  that are contained in Z(f)  . Similarly, we denote by \Pi_0  the set of planes of \Pi  that are fully contained in Z(f)  , and set \Pi'=\Pi\setminus\Pi_0  . For 1\le i \le t  , we let {\cal P}_i  denote the set of points that are contained in the i  -th cell and we let \Pi_i  denote the set of planes that intersect the i  -th cell. Notice that

I({\cal P},\Pi) = I({\cal P}_0,\Pi_0) + I({\cal P}_0,\Pi') + \sum_{i=1}^t I({\cal P}_i,\Pi_i).

We bound each of these three expressions separately. By factoring f  into irreducible factors, we notice that it has O(n^{1/5})  linear factors, and thus Z(f)  fully contains only O(n^{1/5})  planes (that is |\Pi_0|=O(n^{1/5})  ). This immediately implies I({\cal P}_0,\Pi_0) = O(n\cdot n^{1/5}) = O(n^{6/5})  . We next bound \sum_{i=1}^t I({\cal P}_i,\Pi_i)  , for which we require an upper bound on the number of cells t  . We recall Warren’s theorem:

Theorem 2 (Warren’s Theorem). Given a polynomial f \in {\mathbb R}[x_1,\ldots, x_d]  of degree k  , the number of connected components of {\mathbb R}^d \setminus Z(f)  is O\left((2k)^d\right)  .

In our case, Theorem 2 implies t = O((n^{1/5})^3) = O(n^{3/5})  . We set m_i=|{\cal P}_i|\le n^{2/5}  and n_i = |\Pi_i|  . To derive an upper bound for the number of cells that a plane \pi\in\Pi'  can intersect, we define the curve c_\pi = \pi\cap Z(f)  . We can consider c_\pi  as a planar curve of degree O(n^{1/5})  in the plane \pi  , and thus Theorem 2 implies that the number of connected components of \pi\setminus Z(f)  is O(n^{2/5})  . Since any such connected component intersects a single cell of the partitioning {\mathbb R}^3\setminus Z(f)  , we get that \pi  intersects O(n^{2/5})  cells of the partitioning {\mathbb R}^3\setminus Z(f)  . Therefore, \sum_{i=1}^t n_i= O(n^{7/5})  . According to the Cauchy-Schwarz inequality, we have

\sum_{i=1}^t n_i^{1/2} \le \sqrt{\left(\sum_{i=1}^t n_i\right)\left(\sum_{i=1}^t 1\right)} = O\left(\sqrt{n^{7/5}\cdot n^{3/5}}\right) = O(n).

Recalling the bound from (1)  , we obtain

\sum_{i=1}^t I({\cal P}_i,\Pi_i) = O\left(\sum_{i=1}^t (m_in_i^{1/2}+n_i)\right)  = O\left(n^{2/5}\sum_{i=1}^t n_i^{1/2} + \sum_{i=1}^t n_i\right) = O(n^{7/5}).

It remains to bound I({\cal P}_0,\Pi')  , for which we require the second partitioning polynomial theorem from the previous post. Since the theorem only handles irreducible polynomials, we factor f  into irreducible factors f_1,f_2,\ldots,f_s  , and apply the theorem for each f_i  separately. Notice that s=O(n^{1/5})  . For each f_i  of degree D_i  (such that \sum_iD_i = O(n^{1/5})  ), we apply theorem to obtain a second partitioning polynomial g_i  , co-prime with f_i  and of some suitable degree E_i\ge D_i  , which we will specify later. (We assume that Z(f)  is composed only of two-dimensional components. One-dimensional and zero-dimensional components are easy to handle. Moreover, the existence of a polynomial partition that is composed strictly of two dimensional components is proved by Zahl.)

We assume that every point of {\cal P}_0  is incident to exactly one of the zero sets Z(f_i)  . If a point p \in {\cal P}_0  is incident to more than one such zero set, we arbitrarily choose one of these sets Z(f_i)  and treat p  as if it were incident only to Z(f_i)  . Let {\cal P}'_i  (resp., {\cal P}_i^0  ) denote the set of points of \cal P  that are contained in Z(f_i)  but not in Z(g_i)  (resp., and in Z(g_i)  ). We say that a cell of {\mathbb R}^3\setminus Z(g_i)  is proper if it contains at least one point of {\cal P}'_i  , and denote the proper cells as C_{i,1},\ldots,C_{i,t_i}  . According to the second partitioning polynomial theorem, we have t_i = O(D_iE_i^2)  and the number of points of {\cal P}_i' \cap C_{i,j}  is O(m'_i/(D_iE_i^2))  for each j  . We let n'_{i,j}  denote the number of planes of \Pi'  that intersect the proper cell C_{i,j}  , and for 1 \le i \le s  put m'_i = |{\cal P}'_i|  . As in the analysis of the first polynomial partition, we need a bound on \sum_{j=1}^{t_i}n'_{i,j}  .

Lemma 3. Let f,g \in {\mathbb R}[x,y,z]  be co-prime polynomials of degrees D  and E  , respectively, such that D\le E  . Let \pi  be a plane in {\mathbb R}^3  such that \pi\nsubseteq Z(f)  . Then the number of cells of {\mathbb R}^3 \setminus Z(g)  that are intersected by \pi \cap Z(f)  is O(DE)  .

Let f_\pi  (resp. g_\pi  ) denote the bivariate polynomial which is the restriction of f  (resp., g  ) to the plane \pi  . Notice that f_\pi  is of degree at most D  and g_\pi  is of degree at most E  . Every cell of {\mathbb R}^3 \setminus Z(g)  that is intersected by \pi \cap Z(f)  contains at least one connected component of \bigl(\pi \cap Z(f)\bigr) \setminus Z(g)  . Thus, the number of cells is upper bounded by the number of connected components of \bigl(\pi \cap Z(f)\bigr) \setminus Z(g)  , or equivalently, of Z(f_\pi) \setminus Z(g_\pi)  . Each such connected component is either a full connected component of Z(f_\pi)  , to which we refer as a type A component, or an open portion of Z(f_\pi)  whose closure meets Z(g_\pi)  , to which we refer as a type B component. According to Harnak’s curve theorem, Z(f_\pi)  has O(D^2) = O(DE)  connected components, so this is an upper bound on the number of type A components.

Consider a sufficiently small constant \varepsilon>0  , and let g_\pi^+ = g_\pi+\varepsilon  and g_\pi^- = g_\pi-\varepsilon  . By choosing a generic value of \varepsilon  , we may assume that f_\pi  and g_\pi^+  share no nontrivial factors, and that the same holds for f_\pi  and g_\pi^-  . (Indeed, if f_\pi  and g_\pi^+  have a nonconstant common factor p  for two distinct values \varepsilon_1  and \varepsilon_2  of \varepsilon  , then p  divides \varepsilon_1 - \varepsilon_2  , which is impossible. Therefore, the number of “bad” values of \varepsilon  is at most twice the number of components of f_\pi  , which is at most 2D  .) Notice that every type B component must intersect either Z(g_\pi^+)  or Z(g_\pi^-)  (or both). An example is illustrated in the following figure. (On the last part, the blue curves represent Z(f_\pi)  and the red dashed curves represent Z(g_\pi)  . On the right part, the blue curves represent Z(f_\pi)\setminus Z(g_\pi)  and the orange curves represent Z(g_\pi^+)  and Z(g_\pi^-)  .)

PlusMinusEpsilon

This might not true if Z(g_\pi^+)  or Z(g_\pi^-)  contain zero-dimensional components, but a simple technical analysis overcomes this difficultly (Once again, by the analysis of Zahl, we may assume that Z(g)  consists only of two-dimensional components. Let \vec{v}  be the direction of the normal of \pi  . Then we can replace Z(g)  with a copy of it that is translated by an \varepsilon  in the direction of \vec{v}  ). Since g_\pi^+  is of degree at most E  , according to Bézout’s theorem, the number of intersection points between Z(g_\pi^+)  and Z(f_\pi)  is O(DE)  (and the same holds for the number of intersection points between Z(g_\pi^-)  and Z(f_\pi)  ). Therefore, the number of type B components is O(DE)  , concluding the proof of the lemma.     \Box

By Lemma 3, for every 1\le i \le s  we have \sum_{j=1}^{t_i}n'_{i,j} = O(n D_i E_i)  . According to the Cauchy-Schwarz inequality, we have

\sum_{j=1}^{t_i} n'^{1/2}_{i,j} \le \sqrt{\left(\sum_{j=1}^{t_i} n'_{i,j}\right)\left(\sum_{j=1}^{t_i} 1\right)} = O\left(\sqrt{n D_i E_i\cdot D_iE_i^2}\right)  \ \ \ \ = O(n^{1/2}D_iE_i^{3/2}).

Similarly to the preceding analysis, by applying (1)  we have

I({\cal P}'_i,\Pi') = O\left( \sum_{j=1}^{t_i} \left(\frac{m'_i}{D_iE_i^2}n_{i,j}'^{1/2} + n'_{i,j}\right) \right)   = O\left( \frac{m'_i}{D_iE_i^2} \sum_{j=1}^{t_i} n_{i,j}'^{1/2} + \sum_{j=1}^{t_i} n'_{i,j} \right)  \ \ \ \ \ \ = O\left( \frac{m'_i}{D_iE_i^2}n^{1/2}D_iE_i^{3/2}  + n D_i E_i \right)   = O\left( \frac{m'_in^{1/2}}{E_i^{1/2}} + nD_iE_i \right). \ \ \ \ \ (2)

It remains to bound the number of incidences with points of {\cal P}^0_i  .

Lemma 4. Let f,g \in {\mathbb R}[x,y,z]  be co-prime polynomials of degrees D  and E  , respectively, such that D\le E  . Let \Pi'  be a set of n  planes in {\mathbb R}^3  such that no line is fully contained in three planes of \Pi'  and no plane of \Pi'  is fully contained in Z(f)  . Let {\cal P}^0  be a set of m  points in {\mathbb R}^3  such that {\cal P}^0 \subset Z(f)\cap Z(g)  . Then I({\cal P}^0,\Pi') = O(nDE + mDE)  .

Proof.     There are O(E)  planes of \Pi'  that are fully contained in Z(g)  , and these yield O(mE)  incidences with the points of {\cal P}^0  . Let \Pi''  denote the set of planes of \Pi'  that are not fully contained in Z(g)  . See the following figure for an example of a plane \pi  with the intersections of Z(f)  and Z(g)  on it (the red curves represent Z(f)\cap \pi  , the blue curves represent Z(g)\cap \pi  , the purple curves represent curves of Z(f)\cap Z(g)\cap \pi  , and the purple points represent {\cal P}^0_i\cap \pi  ).

PlaneAndTwoSurfaces

We first consider incidences between the plane \pi \in \Pi''  and points of {\cal P}^0_i  that are on a zero-dimensional component of Z(f) \cap Z(g) \cap \pi  . The number of zero-dimensional components of Z(f) \cap Z(g) \cap \pi  is an upper bound on the number of such incidences with \pi  . We consider the two planar curves Z(f)\cap \pi  and Z(g)\cap \pi  of degrees at most D  and E  , respectively. We remove from these two curves one-dimensional components that are common to both of them, and denote the resulting curves as \gamma_f  and \gamma_g  . Bézout’s theorem implies that the number of points in \gamma_f \cap \gamma_g  is O(DE)  . By Milnor’s theorem, the removed common components contain O(D^2) = O(DE)  connected components. Thus, the overall number of zero-dimensional components in Z(f) \cap Z(g) \cap \pi  is O(DE)  , and summing up over all the planes of \Pi''  yields the bound O(nDE)  .

It remains to consider incidences between a plane \pi \in \Pi''  and points of {\cal P}^0  that are on a one-dimensional component of Z(f) \cap Z(g) \cap \pi  . We consider a point p\in {\cal P}^0  , and bound the number of such incidences that p  can participate in. A curve that is fully contained in more than one plane of \Pi''  is a line. According to the assumption, at most two planes of \Pi''  can contain such a line. The intersection Z(f) \cap Z(g)  contains O(DE)  irreducible curves (one way to prove this property is by using resultants, which I plan to discuss in following posts) and each such curve is contained in at most two planes of \Pi''  , so O(DE)  planes can be incident to p  , with a total of O(mDE)  incidences of this type.     \Box

Combining Lemma 4 and (2)  (and recalling that \sum_i m'_i= O(n)  ), we have

I({\cal P}'_i \cup {\cal P}^0_i,\Pi') = O\left( \frac{m'_in^{1/2}}{E_i^{1/2}} + (n+m'_i)D_iE_i\right) = O\left( \frac{m'_in^{1/2}}{E_i^{1/2}} + nD_iE_i\right).

To optimize these expressions, we set E_i = \max \left\{\frac{m_i'^{2/3}}{n^{1/3}D_i^{2/3}},D_i\right\}  for each 1\le i \le s  . The second term dominates when D_i\ge m_i'^{2/5}/n^{1/5}  . Assuming that this is indeed the case, implying E_i=D_i  , we get

I({\cal P}'_i \cup {\cal P}^0_i,\Pi) = O\left( \frac{m'_in^{1/2}}{D_i^{1/2}} + nD_i^2\right) = O\left( nD_i^2\right).

Otherwise, D_i\le m_i'^{2/5}/n^{1/5}  , and thus we have

I({\cal P}'_i \cup {\cal P}^0_i,\Pi) = O\left( \frac{m'_in^{1/2}}{E_i^{1/2}} + nD_iE_i\right) = O\left( m_i'^{2/3}n^{2/3}D_i^{1/3}\right).

Summing up over the cases where D_i\ge m_i'^{2/5}/n^{1/5}  and recalling that \sum_iD_i=O(n^{1/5})  , we have

\sum_{i=1}^s O\left( nD_i^2\right) = O\left(n\left(\sum_{i=1}^sD_i\right)^2\right) = O\left(n^{7/5}\right).

Summing up over the cases where D_i\le m_i'^{2/5}/n^{1/5}  and applying Hölder’s inequality, we have

\sum_{i=1}^s O\left( m_i'^{2/3}n^{2/3}D_i^{1/3}\right) = O\left( n^{\frac{2}{3}}\left(\sum_{i=1}^s m_i\right)^{\frac{2}{3}}\left(\sum_{i=1}^s D_i\right)^{\frac{1}{3}}  \right)  = O(n^{2/3}n^{2/3}n^{1/15}) = O(n^{7/5}).

By combining the above, we obtain I({\cal P}_0,\Pi') = O(n^{7/5})  , which completes the proof.    \Box

After going over the proof of Theorem 1, it is hopefully clearer why so far the technique was used only in {\mathbb R}^3  . For example, when applying the technique in {\mathbb R}^4  we expect the intersection of the two partitions to be a set of two-dimensional surfaces. It is currently unclear how to bound the number of incidences on these surfaces. One approach would be to partition these surfaces by considering a third partitioning polynomial that shares no common factors with each of the first two polynomials. However, it is not known whether such a third polynomial with a sufficiently small degree exists. Similarly, when considering an incidence problem in {\mathbb R}^d  , we would like to use d-1  partitioning polynomials with no factors that are contained in more than one of these polynomials. Proving that the existence of such polynomials of sufficiently small degrees is currently one of the main challenges in the study of polynomial partitioning.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s