"Simen Kvaal" <sim### [at] studentmatnatuiono> writes:
> 
> the vector a_n which points from the centre of circle number n to the point
> P (insode) in question, has an absolute value _less_ than 1. The vector b_n,
> pointing to the point Q _outside_all of the circles, however, has an
> absolute value _equal_ to one.
> 
> Examining the perimeter of the union of the circles, we find m candidates to
> the point Q, and these lie in the corners where circles meet. There are a
> maximum of N+1 such points, but it can be less. 

No. Without loss of generality we assume that all circles are pairwise
different. (If two circles are identical, we remove one of them.)
Since there exists a point that lies inside all circles, two of them
intersect in two points. There are N circles and therefore N*(N-1)/2
unordered pairs of circles. This may lead to up to N*(N-1) intersections.

> It sould not be difficult to locate those points, checking the distance to P
> and chose the one(s) closest.

The closest intersection point may not be the correct solution. It may
lie inside another (third) circle.

A simple but time consuming algorithm may work like this:

1. For every pair of circles find the two intersection points and collect
   them in a list L.
2. For every circle C
3.     For every intersection point P in L
4.        If P is inside C 
5.           Remove P from the list L
6. Find the closest point in L

Thomas

-- 
http://thomas.willhalm.de/ (includes pgp key)

Post a reply to this message