"Simen Kvaal" <sim### [at] studentmatnatuiono> writes:

> >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.
> >
> 
> But most of these intersections are not interesting, because they are
> obscured by other circles. On the _perimeter_ of the big buch of circles,
> there are a maximum og N+1 points to check.
> 
> 
> Try to draw circles on a paper so that all of them overlap at some point,
> and see what happens. How many points around the edge of the figure do you
> need to count?

The problem is that you don't know in advance which intersection points
are on the boundary. You must have a look at all intersection points and
decide whether it is inside another circle. Such a brute force algorithm
requires cubic run time.

However in this case, there is a better way than a brute force algorithm:
Since all circles have the same perimeter, it should be enough to have 
a look at intersection points of consecutive circles, thus considering 
only N intersection points.

Sorting the circles is possible in O(n log n) time. This dominates the
(asymptotic) run time.

Thomas

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

Post a reply to this message