Question

How to find max non-intersecting subset of circles ?
(Given center coordinate and radius of each circle)
Need algorithm that better than O(N²)

Answer 1

We can simply reduce this problem to unweighted interval scheduling problem and make it done in O(nlogn) time.

To do this we have to do some manipulation.

THE ALGORITHM FOR THE PROBLEM IS GIVEN BELOW:

1. We are given centre coordinate and radius of each circle. Lets say centres are in (x,0) format. So say array C[] contains the centre coordinates and array R[] contains radius of each circles.

2. Given R[] and C[] we compute the first point and end point of the diameter of each circle. Say S[] contains the starting points of the diameter computed by the formulae (R[i]-C[i]) for all i. Similarly say E[] contains the ending points of the diameter computed by formulae (R[i]+C[i]).

3. Now form a composite array P[] with {S[i], E[i]} pairs for all i.

4. Sort the composite array P[] on the basis of ending points i.e. E[i]'s.

5. Form array NIC[] denoting sets of non intersecting circles. Add P[1] into NIC[].

6. j=1

7. FOR(i=2 to N) // Assuming N is the total number of circles

IF(The starting point of P[i] is less than ending point of P[j])

then continue

Else

j=j+1

Add P[i] to NIC[j+1]

8. NIC[] will contain all the {centre, radius} pairs for the non intersecting circles.

COMPLEXITY ANALYSIS:

Sorting using merge sort will take O(nlogn) time and after that we do a linear scan to eliminate intersecting circles which will take O(n) time. SO overall complexity will be O(nlogn) which better than O(n).