Question

I am not a specialist in maths, so I thank you very much for any help you can give me.

Consider two circles C1, C2.

Q1: Find the points that are in the intersection of C1 and C2, this is easy !

Q2: Find two points p1 and p2, such that (p1 \in C1) and (p2 \in C2), and (distance(p1, p2)= D). Is it possible to solve this problem ?

Now I want to generalize it to more than two circles and to arbitrary geometric predicates (or patterns)

Consider the circles C1, C2, ..., Cn

Q3: Find the points (p1 \in C1), (p2 \in C2), ... , (pn \in Cn) such that (Some_Geometric_Predicate(p1, ..., pn)= true).

Have you encountered this problem before ? are they any references that speak about such kind of problems ?

Thank you in advance for your help.

Answer 1

Permit me to reformulate a specific version of Q3 that Ellipsissi posed in the comments:

P1. Given three non-intersecting circles $\{C_1,C_2,C_3\}$, find all triples $\{p_1,p_2,p_3\}$ with $p_i \in C_i$ such that $\triangle p_1 p_2 p_3$ is similar to a given triangle $T$.

This differs from the posed question in (a) the non-intersecting condition, and (b) not demanding that a specific angle be realized at a specific corner $p_i$. The form above is analogous to this problem:

P2. Given a plane curve $\gamma$, find all triples $\{p_1,p_2,p_3\}$ of points on $\gamma$ such that $\triangle p_1 p_2 p_3$ is similar to a given triangle $T$.

Much is known about P2, under various restrictions on $\gamma$. For example, if $\gamma$ is a smooth Jordan curve, then I believe it is almost completely understood now, through recent work of Benjamin Matschke, and of Jason Cantarella, Elizabeth Denne, and John McCleary. See especially Cantarella's fascinating web pages on the topic.

So, here is a high-level plan for P1. Connect the three circles by thin corridors to form a plane curve $\gamma$. Solve P2, and discard solutions with points on the corridors, or more than one point on one $C_i$. The efficacy of this plan depends on the degree to which P2 is completely solved in its various guises.

References

1. M. J. Nielsen. "Triangles inscribed in simple closed curves," Geometriae Dedicata 43: 291-297 (1992).

2. Benjamin Matschke. "On the Square Peg Problem and some Relatives." arXiv (2009)

3. Wikipedia article on the Inscribed Square Problem, with triangles discussed under "Variants."

Answer 2

I assume that "geometric predicate" is a logical formula involving known number of points, segments, etc, built from elementary predicates of Euclidean geometry ("this point lies on this line", "these two angles are equal" and the like) using boolean logic and quantifiers.

Then there is an algorithm that reads the text of this logical formula and coordinates and radii of the circles (assuming they are finite decimal numbers, or otherwise "exact") from its standard input, consumes extraordinary amount of memory and CPU cycles, but finally answers whether a solution (or many solutions) exist, and if yes, prints one of them with a given precision.

This works by translating the geometric question into a question about real numbers (coordinates) and using some algorithm implementing Tarski's theorem.

Probably the program will run too long for all but very short formulas. Of course, there may be more efficient algorithms for some specific problems of this type. Or someone may invent better general algorithm in the future.

Answer 3

Let me address just Q2. The set of points at distance $D$ from a point $p_1$ in $C_1$ form an annulus centered on the center of $C_1$, of outer radius $D+r_1$ and inner radius $\max \{ D-r_1, 0 \}$. So you just intersect this annulus with $C_2$, obtaining (in general) zero, one, or two arcs of $C_2$ for the locus of $p_2$ points that are distance $D$ from some point $p_1$. Edit. See Sergei's comment below; I likely misinterpreted "p1 \in C1," which I read as "in" rather than $\in$.

Answer 4

Dear Joseph, thank you very much for your response and the references. It helps me a lot. I was not sufficiently precise in my question: my three circles can be intersecting, so I think that the solution should be simpler (?). For example, i can have the three following circles (from an example on which I work):

C1: $x^2+(y-3)^2 = 9$

C2: $(x^{\prime}+3) ^2+y^{\prime 2} = 9$

C3: $(x^{\prime\prime}+3)^2+ y^{\prime\prime 2}=16$

$(x_a, y_a)=(17/6, 4) \in C1$

$(x_b, y_b)=(-17/6, 4) \in C1$

$p_1= (x,y)$, $(x_a, y_a)$ and $p_2=(x^\prime, y^\prime)$ are aligned

$p_1= (x,y)$, $(x_b, y_b)$ and $p_3=(x^{\prime\prime}, y^{\prime\prime})$ are aligned

$\dfrac{(x-x^{\prime\prime})^2+(y-y^{\prime\prime})^2}{(x^\prime-x^{\prime\prime})^2+(y^\prime-y^{\prime\prime})^2}= \alpha$

$\dfrac{(x-x^{\prime\prime})^2+(y-y^{\prime\prime})^2}{(x-x^{\prime})^2+(y-y^{\prime})^2}= \beta$

$\alpha$, $\beta$, $(x_a, y_a)$ and $(x_b, y_b)$ are known.

The output (the triangle to find) is : $p_1=(x,y)$, $p_2=(x^\prime, y^\prime)$ and $p_3=(x^{\prime\prime}, y^{\prime\prime})$.

One angle of the triangle to find (the one in the corner $p_1=(x,y)$) can be implied from the 1st equation, it is equal to the inscribed angle formed by $(x_a, y_a)$, $(x_b, y_b)$ and $(x,y)$.

I think that since I have some additionnal constraints (the 6th and 7th equations) my problem should be easier to solve. I drawed this in GeoGebra and I could find numerically the solution, but I don't know how to solve it analytically.

Does anyone have any idea ? Thank you in advance.