# Maximum number of points in convex position on a grid made by two sets of concentric circles

Here is a similar but more difficult problem than the one I asked already:

Consider two points $p_1$ and $p_2$ in the euclidean plane and a set of $n$ concentric circles around $p_1$ and a set of $m$ concentric circles around $p_2$, what is the maximum number of points in convex position on the grid made by intersection of these two families of concentric circles?

Remark: (with condition) what if $p_1$ and $p_2$ be two of these convex points and other points said to lie on one side of the line $p_1 p_2$ ? (I mean when $p_1$, $p_2$ and $N-2$ other points (which are from the grid) form a convex $N$-gon, how large this $N$ can be in terms of n and m ? (my own guess: $N$ is of order $m+n$, $N$ can not be multiplicative in $n$ and $m$)

(i think this problem is solvable but hard , and absolutely worth thinking on .thank you )

• Does each circle around $p_1$ intersect each circle around $p_2$ at two points? Aug 6, 2017 at 5:05
• not in the general case....some circles may not intersect ...we are looking for the maximum in the general case , and in general case we can not assume that every two circle intersect Aug 6, 2017 at 6:45

It seems that the answer is really $2mn$ for the original question (and $mn+2$ for the question in the remark) --- i.e., all the points can be in a convex position!

Start with the following recursive construction. Take a semicircle $\Omega$ centered at $O_1$. Take a point $O_2$ on the diameter to the right of $O_1$. Take a point $A_1\in \Omega$ to the left of $O_2$; let the line through $A_1$ perpendicular to $O_2A_1$ meet $O_1O_2$ at $B_1$ (then $B_1$ is outside $\Omega$). Choose $A_2$ on the arc of $\Omega$ lying inside $\triangle O_2A_1B_1$ and proceed in the same way (see figure below). Now, take circles $\beta_1,\dots,\beta_m$ centered at $O_2$ and passing through $A_1,\dots,A_m$. Take $n$ circles $\alpha_1,\dots,\alpha_n$ centered at $O_1$ and sufficiently close to $\Omega$. Their pairwise points of intersection are close to the $A_i$ (and to their reflections in $O_1O_2$). If we take a broken line of all such points of intersection with $\beta_i$ (which are around $A_i$), the directions of all its edges will be close to the direction of the tangent to $\beta_i$ at $A_i$ --- i.e., to $A_iB_i$.

Let $\mathcal H_i$ be the half-plane of the line $A_iB_i$ containing $O_2$. The intersection of all the $\mathcal H_i$ ($i=1,2,\dots,m$) is a convex polygonal region, with all the $A_i$ on its boundary. Thus, connecting our broken lines together we will get a convex broken line. (Pitifully, the points become too close, so I could not make a good picture of it...)

Finally, this resulting broken line can be augmented by either $O_1$, $O_2$ or its reflected image, by your wish, to obtain a convex polygon.

• @GunterRote: THanks for editing; you also could just tell me that the figure has a typo... Sep 24, 2017 at 22:15