7
$\begingroup$

Let $k$ be a fixed positive integer. We want to find the minimum number $f(k)$, such that for a set of finite points in the plane, if any $f(k)$ of them are on $k$ circles, then all of them are on $k$ circles.

For example $f(1)=4$ (trivial) and $f(2)=9$.

Can you find some bounds for $f(k)$?

p.s. We know the answer for "line" instead of "circle" is $f(k)=\binom{k+2}{2}$.

Improve this question
$\endgroup$
8
  • $\begingroup$ I think providing some more related results and links would be useful. $\endgroup$
    – domotorp
    Commented Feb 8, 2015 at 22:27
  • $\begingroup$ The number $f(k)-1$ is also the minimum $n$ such that for any set of $n$ points $S$ in the plane there is at most a union of $k$ circles $X=C_1\cup\dots\cup C_k$ such that $S\subset X$, isn't it? $\endgroup$
    – Pietro Majer
    Commented Feb 9, 2015 at 0:43
  • $\begingroup$ Although I don't doubt it, I would appreciate a proof sketch that $f(2)=9$. $\endgroup$
    – Joseph O'Rourke
    Commented Feb 9, 2015 at 0:57
  • $\begingroup$ An interesting variant might be to replace "$k$ circles" by "$k$ unit-radius circles." $\endgroup$
    – Joseph O'Rourke
    Commented Feb 9, 2015 at 0:58
  • 1
    $\begingroup$ @JosephO'Rourke The sketch of proof for f(2)=9 is using some cases for those nine points, 5+4 or 6+3 or..., then replacing one of them with the new point (10th point). The counterexample for 8 is three circles with their pairwise intersections (6 points) and one extra point on each of them. I think the answer for "unit circles" is very small. $\endgroup$
    – Morteza
    Commented Feb 9, 2015 at 12:18

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .