# Set of points in the plane which is intersected by every line on the plane and in which no more than K points are collinear

• Question Let $K \in \mathbb{N} (K \geq 3)$ and $r \in \mathbb{R}^+$. Either find a set $S$ of points in the plane such that every line on the plane intersects atleast one point in $S$ and that no more than $K$ points in $S$ are collinear, or prove that there is no such set.
• *As an additional constraint the points should be so distributed that every circle disc of radius r on the plane has at-least one point which belongs to S*

References on related results would also be nice.

Remark: The question is a kind of non-connected version of this question " find a curve which intersects all lines on the plane at most $K$ times and at least once."

In a more general setting, we may replace the 'circledisc' constraint by a chosen statistical distribution of points.

EDIT

By finding it would be correct to mean a constructive proof

## migrated from mathoverflow.netSep 23 '13 at 21:17

This question came from our site for professional mathematicians.

• What do you mean by "devise"? – Igor Rivin Sep 23 '13 at 18:19
• Can't I just start with some lattice with small enough mesh to easily meet every $R$-disc, and then randomly perturb each point? If you want a completely explicit configuration, enumerate the lattice points any way you lik and then move the $n$-th one by $(a_n\pi^{2^{2n+1}}, b_n\pi^{2^{2n+2}})$ for some nonzero rational $a_n,b_n$ small enough that the perturbation is less than half the shortest lattice vector. – Noam D. Elkies Sep 23 '13 at 18:55
• @ARi: I tried to improve the formulation of your question. This involved significant rephrasing, so please check. – Stefan Kohl Sep 23 '13 at 20:02
• At least right now, the question asks for a set which meets every circle, not every disk. You can just do it (meaning, well-order the circles and choose appropriate points by transfinite induction). Were you hoping for something more explicit? – James Cranch Sep 23 '13 at 20:27
• @StefanKohl thanks. a little rework and now it fine – ARi Sep 24 '13 at 9:15

Clearly $K$ must be at least $2$. Under AC (the Axiom of Choice), $K=2$ can be attained, even if we require $S$ to meet every circle, not just circles of fixed radius. The construction uses transfinite induction, so "finds" $S$ only in a somewhat weak sense...

The set of lines and circles in the plane, call it $\Sigma$, has cardinality $c$ (continuum). Using AC we can well-order $\Sigma$ so for each $\alpha \in \Sigma$ there are fewer than $c$ lines and circles preceding $\alpha$ in the order. We now construct $S = \{ p_\alpha : \alpha \in \Sigma \}$, where each $p_\alpha \in \alpha$ is chosen inductively so that it is not collinear with $p_\beta$ and $p_\gamma$ for any distinct $\beta,\gamma \prec \alpha$. This is possible because there are $c$ points in $\alpha$ but the cardinality of lines $\overline{p_\beta p_\gamma}$ with $\beta,\gamma \prec \alpha$ is less than $c$ (if a set has cardinality less than $c$ then so does its square), and each line meets $\alpha$ in at most two points. This fails only if $\alpha$ happens to be the line joining some $p_\beta$ and $p_\gamma$, but then $\alpha$ already has a point of $S$ so we can skip $\alpha$ (or declare that $p_\alpha = p_\beta$). Then $S$ meets every line and every circle, and contains no three collinear points.

The same trick applies in greater generality; e.g. $S$ can be made to meet every algebraic curve and have neither three collinear nor four concyclic points.

(All this must be known already, but it's easier to write a proof than find a reference.)

[Added later I see now that James Cranch suggested this approach in his comment on this question on mathoverflow before it was migrated here.]

• Very interesting; specially since you prove a stronger result of S meeting every circle.. a result which initially appears counter intuitive. I wonder though what would be an algorithmic approach to construct S. Say the first point in S is at origin the algorithm should give out the nth point for n as input. – ARi Sep 27 '13 at 10:48
• In addition to above the algorithm; given any line (a,b) outputs ($x_i,y_i$), 0<i<3 ; The three (max) collinear points which are on it and on given a disc D cantered at (x,y) and radius r; outputs the coordinates of 'a' Point p$\in S \; and \; p \in D$ – ARi Sep 27 '13 at 17:43
• @ARi: The problem is that we don't have an explicit well-order that is needed, and we can't define most of the points on a line. We could say the well-order starts with $y=0, x^2+y^2=1, x=0,$ etc. The first point can be at the origin, but the next point can be anywhere on the unit circle and the next one can be almost anywhere on the $y$ axis. – Ross Millikan Sep 27 '13 at 19:52
• @RossMillikan So do we take it that, while set $S$ would exist, it is not describable (as an extensional definition) by any mathematical function ? And while there may be infinite sets which qualify as $S$ our algorithm needs to construct only one. – ARi Sep 27 '13 at 20:19
• @ARi: that is correct. I believe there will be continuum many, but without AC there may not be one. – Ross Millikan Sep 27 '13 at 20:21