1
$\begingroup$
  1. The unit distance problem in the plane asks for the maximum number $U(n)$ of unit distances which can be obtained by $n$ points.
  2. For $k$ unit circles and $m$ points in the plane, $I(k,m)$ counts the number of point-circle incidences.

Now, in Matousek's Discrete Geometry book, he claims that $U(n) \leq \frac{1}{2} I(n,n)$, but my questions is shouldn't it be $U(n) \leq \frac{1}{2} I(n,2n)$, since any two circles possibly intersect in two points?

1 Answers 1

1

$I(n,n)$ is correct: Take $n$ points realizing $U(n)$ unit distances and draw a unit circle around each. Each pair of points corresponds to two unit circles, which gives you two point-circle incidences. In other words, it takes two points in the unit-distance problem to produce two incidences in the point-circle problem, so the number of points in the $U$ function and the $I$ function should be the same.

  • 0
    @stefan The unit circles could be arranged in such a way that not all the point-circle incidences are distinct (so we wouldn't get the full $I(n,n)$ incidences). In the case were all the incidences are distinct, then I guess we do get equality, though I would want to think about it more before I bet my house on it.2012-09-19