2
$\begingroup$

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 )

$\endgroup$
2
  • $\begingroup$ Does each circle around $p_1$ intersect each circle around $p_2$ at two points? $\endgroup$ Aug 6, 2017 at 5:05
  • $\begingroup$ 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 $\endgroup$
    – Khandan
    Aug 6, 2017 at 6:45

1 Answer 1

3
$\begingroup$

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

Recursice construction

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.

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

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.