# Match set of points in set of circles

• Aug 6th 2008, 04:20 PM
seson
Match set of points in set of circles
Hi,

I have a set of points (px_i, py_i) and each point is linked to a circle with (cx_i, cy_i and radius r_i).

The set of points can be moved, the set of circles can be moved, too. I.e. the pattern of the points and circles, respectively, is fixed and has to remain. Put in other words, only all circles or points, respectively, can be moved at the same time.

"All" I want to know is if it's possible to move the set of points so that each point is within its linked circle.

This used to be my approach, but it fails:
- Move all points so that point 1 is in the center of circle 1.
- loop i over the rest of the points inside the set
- move the set of points so that point i is inside circle i (not in the center, but inside)

After that I thought if there's a solution, I would get it. But apparently there're sometimes more solutions and my algorithm doesn't always solve it even though there is a solution.

I'm sure there's a way or this has been proven by someone already, it seems like a common problem.

The circle part can be rephrased. Instead of circle, you can use another point (cx_i, cy_i) and add the constraint that p_i should have the maximum distance of r_i from this point. (Which is basically the same.)

Regards,
Sebastian