How many small dots can be drawn in a region such that no three are "collinear"?

Question

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.

Answer 1

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

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.

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.

Answer 2

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.