The Elekes-Sharir Framework (part 3)

In the previous posts of this series (part 1 and part 2), we discussed the history of the Elekes-Sharir reduction, the basic technical details, and applied the reduction to reprove a result of Szemerédi. In this post, the third and final one of the series, we present another application of the reduction.

Let {\cal P}_1  (resp., {\cal P}_2  ) be a sets of m  (resp., n  ) points, all on a common line \ell_1  (resp., \ell_2  ). Let D({\cal P}_1,{\cal P}_2)  denote the number of distinct distances between the pairs of {\cal P}_1\times{\cal P}_2  (that is, only distinct distances between points on different lines are considered). There exist configurations where \ell_1  and \ell_2  are either parallel or orthogonal and D_{\text{lines}}({\cal P}_1,{\cal P}_2) = \Theta(\max\{m,n\})  . For example, see the following figure.

Twolines

The case where \ell_1  and \ell_2  are neither parallel nor orthogonal is more difficult and has prompted various works in the past 15 years (see Elekes and Rónyai, Elekes, Schwartz, Solymosi, and de Zeeuw, and Sharir, Sheffer, and Solymosi). Let D_{\text{lines}}(m,n)  denote the minimum number of distinct distances in such a scenario. Elekes observed the subquadratic upper bound D_{\text{lines}}(m,n) = O(\max\{n^2/\log n, m^2/\log m\})  . The best known lower bound D_{\text{lines}}(m,n)=\Omega\left( \min\left\{m^{2/3}n^{2/3},m^2,n^2 \right\}\right)  was recently derived by Sharir, Sheffer, and Solymosi). Notice the large gap between the two bounds — one of the largest among the variants of the distinct distances problem.

We now explain how to derive the lower bound of Sharir, Sheffer, and Solymosi by applying the Elekes-Sharir framework. Recently, we learned that this proof can be slightly simplified by removing the use of the framework from it (see here for more details).

Theorem. (Sharir, Sheffer, and Solymosi)

D_{\text{lines}}(m,n)=\Omega\left( \min\left\{m^{2/3}n^{2/3},m^2,n^2 \right\}\right).

Proof.     Consider a set {\cal P}_1  of m  points (resp., a set {\cal P}_2  of n  points), all on a common line \ell_1  (resp., \ell_2  ). Additionally, the lines \ell_1  an \ell_2  are neither parallel nor orthogonal. We set x=D({\cal P}_1,{\cal P}_2)  and denote the x  distinct distances in {\cal P}_1\times{\cal P}_2  as \delta_1,\ldots, \delta_x  . We apply the Elekes-Sharir framework with a small change. This time, we define

Q =\left\{ (a,p,b,q) \mid a,b\in{\cal P}_1, \quad p,q\in{\cal P}_2, \quad \text{and}\quad |ap|=|bq|>0 \right\}

(Q  does not include quadruples of the form (a,p,a,p)  ). As before, we begin by deriving a lower bound on |Q|  . Let E_i = \{(a,p)\in {\cal P}_1 \times {\cal P}_2 \mid |ap|=\delta_i \}  , for i=1,\ldots,x  . Notice that \sum_{i=1}^x |E_i| = mn  . By the Cauchy-Schwarz inequality, we have

|Q| = 2\sum_{i=1}^x\binom{|E_i|}{2} \ge \sum_{i=1}^x \left(|E_i|-1 \right)^2  \ge \frac{1}{x}\left(\sum_{i=1}^x (|E_i|-1) \right)^2 = \frac{\left(mn -x\right)^2}{x}. \ \ \ \ (1)

Next, we upper bound |Q|  . In this case, no quadruple in Q  can correspond to a translation, so it suffices to bound the number of quadruples that correspond to a rotation. That is, we consider quadruples (a,p,b,q)\in Q  such that there exists a rotation taking a  to b  and p  to dq  . For example, see the following figure.

Rotation2lines

For every pair of points a,b\in {\cal P}_1  , we say that \ell_{ab}  is a blue line (recall the definition of \ell_{ab}  from the first post of the series) and for every pair of points p,q\in {\cal P}_2  , we say that \ell_{pq}  is a red line. Notice that the quadruple (a,p,b,q) \in ({\cal P}_1\times{\cal P}_2)^2  is in Q  if and only if the lines \ell_{ab}  and \ell_{pq}  intersect. That is, in this case we have m(m-1)  blue lines and n(n-1)  red lines, and there is a bijection between the quadruples of Q  and the set of red-blue intersections.

It seems unlikely that a meaningful bound on the number of red-blue intersections can be obtained without any additional information about the lines. Fortunately, these lines are very restricted. Recall that the projection of a line \ell_{ab}  on the xy  -plane is the perpendicular bisector of the segment ab  . The projections of all of the blue lines on the xy  -plane are orthogonal to \ell_1  and are thus parallel to each other (and the same holds for the red lines and \ell_2  ). Moreover, two quadruples in Q  cannot correspond to the same rotation; this is almost immediate from the fact that any rotation with an origin not on \ell_1  can take at most one point of \ell_1  to a point of \ell_1  . It is not difficult to find other restrictions on these lines, such as that all the blue lines intersect the instance of \ell_1  on the xy  -plane, and that all the red lines intersect the instance of \ell_2  on the xy  -plane. Such a configuration is depicted in the following figure.

TwoLines3d

To simplify the analysis, we rotate and translate the plane so that \ell_1  becomes the x  -axis and \ell_1 \cap \ell_2  becomes the origin (0,0)  . This transformation does not have any effect on D({\cal P}_1,{\cal P}_2)  . Let s  denote the slope of \ell_2  after the rotation. Since \ell_1  and \ell_2  are neither parallel nor orthogonal, s  is finite and nonzero. For a,b\in{\cal P}_1  and p,q\in{\cal P}_2  we have (recalling the line equations from the first post)

\ell_{ab} = \left(\frac{a_x+b_x}{2}, t\cdot\frac{a_x-b_x}{2},t\right), \quad \text{ for } t\in{\mathbb R}, \quad \text{and}  \ell_{pq} = \left(\frac{(p_x+q_x)+t's(q_x-p_x)}{2}, \frac{s(p_x+q_x)+t'(p_x-q_x)}{2},0\right), \quad \text{ for } t'\in{\mathbb R}.

To simplify these equations, we set \phi_{ab} = \frac{a_x+b_x}{2}  and \mu_{ab} = \frac{a_x-b_x}{2} . We can now write

\ell_{ab} = \left(\phi_{ab}, t\mu_{ab},t\right), \quad \text{ for } t\in{\mathbb R}, \quad \text{and}  \ell_{pq} = \left(\phi_{pq}-t's\mu_{pq}, s\phi_{pq}+t'\mu_{pq},t'\right), \quad \text{ for } t'\in{\mathbb R}.

The quadruple (a,p,b,q)  is in Q  if and only if \ell_{ab}  and \ell_{pq}  intersect; that is, if there is a solution to the system

\phi_{ab} = \phi_{pq}-ts\mu_{pq},
t\cdot\mu_{ab} = s\phi_{pq}+t\mu_{pq}.

If we ignore the cases where \mu_{pq}=0  and/or \mu_{ab}-\mu_{pq}=0  (which are easy to handle), then by eliminating t  we get that (a,p,b,q)  is in Q  if and only if

\frac{\phi_{pq}-\phi_{ab}}{s\mu_{pq}} = \frac{s\phi_{pq}}{\mu_{ab}-\mu_{pq}},

or

(\phi_{pq}-\phi_{ab})(\mu_{ab}-\mu_{pq}) = s^2\mu_{pq}\phi_{pq}. \ \ \ \ (2)

To get a bound on the number of pairwise intersecting lines (pairs for which (2)  holds), we apply a second reduction, this time to a parametric plane. For every pair of points p,q\in {\cal P}_2  , which define the red line \ell_{pq}  , we define a corresponding point (\phi_{pq},\mu_{pq})\in{\mathbb R}^2  . For every pair of points a,b\in {\cal P}_1  , which define the blue line \ell_{ab}  , we define a corresponding hyperbola

\gamma_{ab} = (x-\phi_{ab})(\mu_{ab}-y) - s^2xy.

Notice that \gamma_{ab}  is incident to (\phi_{pq},\mu_{pq})  if and only if (2)  holds, so the quadruple (a,p,b,q)  is in Q  if and only if \gamma_{ab}  is incident to (\phi_{pq},\mu_{pq})  . That is, to upper bound |Q|  , it suffices to upper bound the number of incidences between a set \cal H of \Theta(m^2)  hyperbolas and a set {\cal P}'   of \Theta(n^2)  points, both in {\mathbb R}^2  . With the existing tools for solving incidence problems, it appears hard to obtain a good bound on the number of point-hyperbola incidences. Fortunately, the point-hyperbola configuration that we have is degenerate.

By definition, two hyperbolas intersect in at most four points. That is, any pair of hyperbolas from \cal H  can be incident to at most four common points from {\cal P}'  . Moreover, the roles of \ell_1  and \ell_2  (and of {\cal P}_1  and {\cal P}_2  ) are fully symmetric, and can be interchanged, by regarding the pairs of distinct points in {\cal P}_1^2  (resp., {\cal P}_1^2  ) as a set of points (a,b)  in the plane (resp., as a set of hyperbolas \gamma_{p,q}  , defined in a fully symmetric manner). This implies, in particular, that there are at most four hyperbolas of \cal H  that pass through a given pair of points in {\cal P}'  . According to a result by Pach an Sharir, the number of point-hyperbola incidences with such a restriction is O(|{\cal P}'|^{2/3}|{\cal H}|^{2/3} + |{\cal P}'| + |{\cal H}|)  . Thus, we have

|Q| = O(|{\cal P}'|^{2/3}|{\cal H}|^{2/3} + |{\cal P}'| + |{\cal H}|) = O(m^{4/3}n^{4/3} + m^2 + n^2).

Combining this bound with the lower bound in (1)  implies the assertion of the theorem.     \Box

Advertisements

2 thoughts on “The Elekes-Sharir Framework (part 3)

  1. Pingback: Polynomial partitioning: the basics (part 1) | Some Plane Truths

  2. Pingback: The Partial Elekes-Sharir Framework | Some Plane Truths

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