-1
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • $\begingroup$ en.wikipedia.org/wiki/Compass_and_straightedge_constructions In particular, you'll find some key constructions that are impossible. $\endgroup$
    – Austin Mohr
    Commented Sep 17, 2010 at 18:18
  • 1
    $\begingroup$ Q2 is the wrong level for MathOverflow and I'm unclear what exactly you mean by geometric predicates in Q3. $\endgroup$
    – Qiaochu Yuan
    Commented Sep 17, 2010 at 19:20
  • $\begingroup$ @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. $\endgroup$
    – Ellipsissi
    Commented Sep 17, 2010 at 19:50
  • $\begingroup$ 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. $\endgroup$
    – Sergei Ivanov
    Commented Sep 17, 2010 at 20:18
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Sergei Ivanov
    Commented Sep 17, 2010 at 20:39

3 Answers 3

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ The inner radius should be $|D-r_1|$. $\endgroup$
    – Sergei Ivanov
    Commented Sep 17, 2010 at 20:10
  • $\begingroup$ @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. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 17, 2010 at 20:24
  • $\begingroup$ Yes, the meaning is that p1 is on the circle, not in the disk. Thank you for your help. $\endgroup$
    – Ellipsissi
    Commented Sep 17, 2010 at 20:43
  • $\begingroup$ @Ellipsissi: Apologies! So the radius is as per Sergei's correction. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 17, 2010 at 21:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .