3
$\begingroup$

Recall:

Theorem (Szemeredi-Trotter): Given $n$ distinct points and $\ell$ distinct lines in $\mathbb{R}^2$, the number of point-line incidences is $O(n + \ell + (n \ell)^{2/3})$.

Now, instead of $\ell$ lines, suppose we are given a set $S$ of $|S| = s$ points in general position, and the lines are implicitly described as all lines that pass through a pair of these points (so $\ell = {s \choose 2}$). We are also, separately, given a set $N$ of $|N| = n$ distinct points, and we want estimates on the number of incidences between the lines determined by $S$ and the points in $N$.

Clearly the Szemeredi-Trotter theorem still applies, but the lower bound implying optimality of the Szemeredi-Trotter theorem breaks in this setting, so it is conceivable that we could obtain an asymptotically improved estimate. Has this modification been studied before, or are any nontrivial upper or lower bounds known?

Improve this question
$\endgroup$
6
  • $\begingroup$ Exactly what would you like to know? The theorem, of course, is perfectly true in your special case, too. $\endgroup$
    – Seva
    Commented Feb 7, 2018 at 16:46
  • $\begingroup$ @Seva the theorem is certainly true, but the corresponding lower bound that implies optimality of the Szemeredi-Trotter Theorem no longer holds. I am wondering if an asymptotically smaller upper bound can be obtained in this restricted setting. $\endgroup$
    – GMB
    Commented Feb 7, 2018 at 16:51
  • $\begingroup$ That is, you want to improve the estimate in the special case where the set of lines includes all lines determined by our point set, not just some "very reach" lines? $\endgroup$
    – Seva
    Commented Feb 7, 2018 at 16:58
  • $\begingroup$ I think I am misunderstanding your question. It seems to me that if you have $s$ points in general position and consider all lines between them, you will always have exactly $2\binom{s}2$ point-line incidences, exactly two for each line. Is there something I am missing here? $\endgroup$
    – Sean English
    Commented Feb 7, 2018 at 17:05
  • 1
    $\begingroup$ And, BTW, what do you mean by "$s$ points in general position"? This normally means that no line contains three (or more) points. In this case there are exactly two incidences per each of the $\binom s2$ lines, so that there are $2l$ incidences. $\endgroup$
    – Seva
    Commented Feb 7, 2018 at 17:06

0

Reset to default

You must log in to answer this question.