Thursday, July 14, 2011

Fox 345

A 2-circle covering problem would have been easier. But Let's start with this one. 1. Let d be the diameter of the circles, a the distance between the centres of any pair of the three covering circles and b the distance between the centres of the other two pairs.
Each case is obvious if a or b is greater than or equal d, or a = 0 or b = 0.
Now consider a and b less than d and not equal zero, i.e. they overlap (not completely) each other.
sqrt[d^2 + d.sqrt(d^2 - a^2)] / sqrt(2) less than or equal b less than or equal sqrt[d^2 + d.sqrt(d^2 - a^2)] / sqrt(2) to cover the fourth circle of the same diameter d.

jyu

2. correction:

sqrt[d^2 - d.sqrt(d^2 - a^2)] / sqrt(2) less than or equal b less than or equal sqrt[d^2 + d.sqrt(d^2 - a^2)] / sqrt(2) to cover the fourth circle of the same diameter d.

jyu

3. Hi jhu,

Is this what you mean? http://imgur.com/N91lX

if so, why doesn't it depend on distances between origin and covering circles?

Thanks,

4. jyu said
interchange a and b in your drawing was what i meant.
it doesn't depend on distances from the origin because i did not centre the to-be-covered circle at the origin. In other words i did not use coordinates because you will end up with a cumbersome expression to convey the same idea.

5. clarification needed...

initial statement by jyu defines a condition involving a and b where a is the distance btw centers of "any" pair of covering circles, b being the distance btw centers of the "other two pairs".

a) which other two pairs? or is it other two circles?

b) whichever interpretation is right, above picture by imgur does not match (nor does it after interchange of a and b I suspect)

c) if "other two circles" is the correct interpretation, then we can easily find a counterexample because these two circles coordinates are independent from the other two

d) maybe "any pair" should read "for all pairs"...

bleaug

6. hints:

- problem is homothetic to problem where all circles have radius 1

- problem is invariant by rotations centered in O and by all permutations of {P1(x1,y1), P2(x2,y2), P3(x3,y3)}

Hence the "best" representation to formulate the requested conditions seems to transform the problem {x1,y1,x2,y2,x3,y3} into its canonical rep {r1,r2,r3,A,B,C} using polar coordinate system: {P1(r1,0), P2(r2,A), P3(r3,A+B)}, A in [0,2pi], B in [0,2pi-A], C=2pi-A-B

bleaug

7. jyu said
Let P, Q and R be the centres of the covering circles.
Suppose a = PQ, then b = QR or PR

8. jyu said
the inequalities can be further simplified if diameter d is 1 unit

like to see a counterexample, thanks

9. jyu said
I found a counterexample. Thanks.
The inequalities are true if there is an axis of symmetry.

10. Bleaug,
Your observations are correct. If you have a solution based on polar coordinates, we'd love to see it. Then it is no big deal; we can reformat the question accordingly.
Thanks.
-8foxes

11. yes i have ;-)

simply didn't have time to put it in the right shape. But i would be happy to see someone build smthg based on the above hints.

here is my strategy:
- first show that 3 circles of radius r cover a 4th circle of radius r if and only if they cover the circumference (not difficult and quite a nice problem of its own)
- then convert the general (cartesian) problem {x1,y1,x2,y2,x3,y3,r} into (polar) {r1,r2,r3,A,B,C,1} using scaling, rotation and permutation as hinted
- circle of radius ri cover a part of circumference equal to ai=2*arccos(ri/2)
- express conditions between {a1,a2,a3} and {A,B,C} so that circumference is covered
- simplify formulae

hopefully this should give smthg...
bleaug

12. http://imageshack.us/photo/my-images/810/3circles2.png/

jyu

13. jyu said
From the sketch max/min distance between centres, and max/min angle formed by lines joining centres can be determined, independent of the choice of coordinate system and origin.