Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
en.wikipedia.org/wiki/Compass_and_straightedge_constructions In particular, you'll find some key constructions that are impossible. –  Austin Mohr Sep 17 '10 at 18:18
1  
Q2 is the wrong level for MathOverflow and I'm unclear what exactly you mean by geometric predicates in Q3. –  Qiaochu Yuan Sep 17 '10 at 19:20
    
@Austin: Thank you, will take a look @Qiaochu: Q2 is mainly to introduce Q3. Geometric predicate, for example, the points p1, ..., pn should a form a regular polygone, or any defined geometric pattern. –  Ellipsissi Sep 17 '10 at 19:50
    
It is not clear what your "Find" means. Construct with ruler and compass? Find numerically? Determine for which configurations of circles a solution exists? These are very different questions, handled by different areas of mathematics. –  Sergei Ivanov Sep 17 '10 at 20:18
2  
The solution can have coordinates like $\sqrt 2$ for simple integer-valued initial data (centers and radii). What do you mean when you say that an algorithm gives you this exact number? (The usual definition of the word "algorithm" is modelled after our familiar digital computers that don't have infinite-precision real numbers.) –  Sergei Ivanov Sep 17 '10 at 20:39

4 Answers 4

up vote 1 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
1  
The inner radius should be $|D-r_1|$. –  Sergei Ivanov Sep 17 '10 at 20:10
    
@Sergei: Hmmm. If, say, $r_1=10$ and $D=1$, then it seems one obtains a disk of radius 11, rather than an annulus with inner radius $|1-10|=9$? Ah, maybe we are interpreting $p_1 \in C_1$ differently. I was interpreting it as $p_1$ inside the circle, but I see that may be a mistaken assumption. If it means $p_1$ on the circle, then you are correct. –  Joseph O'Rourke Sep 17 '10 at 20:24
    
Yes, the meaning is that p1 is on the circle, not in the disk. Thank you for your help. –  Ellipsissi Sep 17 '10 at 20:43
    
@Ellipsissi: Apologies! So the radius is as per Sergei's correction. –  Joseph O'Rourke Sep 17 '10 at 21:05

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.

share|improve this answer
    
You have a very specific set of equations, and perhaps they could be solved exactly by more powerful algebraic software, such as Maple or Mathematica. I cannot tell myself just by visual inspection; sorry! –  Joseph O'Rourke Sep 18 '10 at 17:49
    
Thank you for the advice, I will do like this, thank you. –  Ellipsissi Sep 18 '10 at 18:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.