When people draw dots on paper, they are actually not points, but small regions filled with ink. Suppose that each dot has disc-shape with fixed radius $r\ll 1$ and must be drawn inside (1) a square region with side length $1$; (2) a circle region with radius $1$. How many dots can be drawn such that no three are collinear? Three dots are collinear if one of them intersects with the strip determined by the other two at more than one point. (I think it is equivalent to: there exists a line that intersects all the dots at more than one point.)

Comment. I was working on an Olympic level problem that requires $100$ points in a circle without any three being collinear. It is a very difficult task with usual pen and paper. So I came up with this problem and hopefully someone has done similar problems before, or can give an algorithm to estimate the bound when $r$ is small.

  • 1
    $\begingroup$ Related: For exact no-three-in-a-line of points on a $n \times n$ grid, the best lower bound is $n(1.5 -o(n))$ and best upper bound is $2n$. Discussed by David Eppstein in Forbidden Configurations in Discrete Geometry. $\endgroup$ – Joseph O'Rourke Aug 26 '19 at 14:41
  • $\begingroup$ @JosephO'Rourke If $r<(2\sqrt{(n-1)^2+n^2})^{-1}\approx (2n)^{-1}$, no line can cross ($2$ or more intersections) three collinear dots on $n\times n$ grids. Then there could be $0.75r^{-1}$ dots based on Hall et al. result? $\endgroup$ – Haoran Chen Aug 27 '19 at 3:14
  • $\begingroup$ Seems correct.${}$ $\endgroup$ – Joseph O'Rourke Aug 27 '19 at 10:45

For a circle, suppose we distribute $n$ dots evenly near the circumference. circles in circle

One dot has a center at $(1-r,0)$ and the adjacent dots have centers at $$((1-r)\cos(2\pi/n),\ \pm (1-r)\sin(2\pi/n))$$ The middle one goes as far to the left as $1-2r$, and the neighbors go as far to the right as $(1-r)\cos(2\pi/n)+r$ To avoid collinearity, we need \begin{align} (1-r)\cos(2\pi/n)+r &< 1-2r\\ n &< 2\pi/\arccos\left(\frac{1-3r}{1-r}\right) \end{align} Asymptotically, this means we can choose $n$ as large as $$\frac{\pi}{\sqrt{r}}\left(1-\frac{2r}{3}+O(r^2)\right)$$ which is a reasonable lower bound for the problem.

For a unit square, $[-1/2,1/2]^2$, putting all the dots on one circle still seems to work well.

We can try an alternative, putting dots on four circular arcs (black, blue, purple, red) each of which stays closer to one of the four sides.

enter image description here

The black arc will have a center at $(-h,0)$, a radius of $k=1/2+h-r$, and a dot with a center at $(1/2-r,0)$.

The dashed lines show radii of the black arc; we call the smallest central angle $\alpha$ and the biggest central angle $\beta$. Then the total number of dots on that arc will be twice the floor of $\beta/\alpha$ where \begin{align} -h+k\cos(\beta)&=k\sin(\beta)\\ -h+k\cos(\alpha)&=1/2-3r \end{align} Empirically, we maximize $\beta/\alpha$ at $h=0$, which is to say that we might as well take the four circular arcs to be part of the same circle. In the diagram, that corresponds to spacing the dots evenly outside the light gray circle instead.


Well one observation is that if three dots are not "collinear" then the triangle formed by all of the centers has the lengths of its altitudes being at least $r$. This implies that the area is at least $\frac{r^2}{\sqrt{3}}$. This relates the problem to the Heilbronn triangle problem which has some bounds.

  • 1
    $\begingroup$ Well, since the circles have to be disjoint, there cannot be more than $O(r^{-2})$ of them. Doesn’t this already give a better bound than using the Heilbronn problem? $\endgroup$ – Emil Jeřábek Aug 26 '19 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.