0
$\begingroup$

  • 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

$\endgroup$

migrated from mathoverflow.net Sep 23 '13 at 21:17

This question came from our site for professional mathematicians.

  • $\begingroup$ What do you mean by "devise"? $\endgroup$ – Igor Rivin Sep 23 '13 at 18:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Sep 23 '13 at 18:55
  • $\begingroup$ @ARi: I tried to improve the formulation of your question. This involved significant rephrasing, so please check. $\endgroup$ – Stefan Kohl Sep 23 '13 at 20:02
  • 1
    $\begingroup$ 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? $\endgroup$ – James Cranch Sep 23 '13 at 20:27
  • $\begingroup$ @StefanKohl thanks. a little rework and now it fine $\endgroup$ – ARi Sep 24 '13 at 9:15
3
$\begingroup$

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.]

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ARi Sep 27 '13 at 10:48
  • $\begingroup$ 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$ $\endgroup$ – ARi Sep 27 '13 at 17:43
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan Sep 27 '13 at 19:52
  • $\begingroup$ @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. $\endgroup$ – ARi Sep 27 '13 at 20:19
  • 1
    $\begingroup$ @ARi: that is correct. I believe there will be continuum many, but without AC there may not be one. $\endgroup$ – Ross Millikan Sep 27 '13 at 20:21

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.