CareerCup

The idea to do a quick screen:
1) For two circles to intersect, x-range and y-range must have overlap.
2) but the reverse is not always true. So need to iterate over the screened result in (1) to check

So,
1) sorted over x-coordination, check each element's sliding window to focus on overlapping ones, and check if y overlaps as well, and then check the r1+r2>distance

NlogN solution
Sort the co-ordinates in x/y axis and binary search for first point on left and right where sum of radius is > distance between centers. all on left from left point and on right from right point will be the set of co-ordinates with non-intersecting circles.

import math

all_intersecting_circles = list()
for a_idx in range(len(circles)):
    a = circles[a_idx]
    intersecting_circles = set()
    intersecting_circles.append(a)
    for b_idx in range(a_idx + 1, len(circles)):
        b = circles[b_idx]
        height = abs(a.y - b.y)
        width = abs(a.x - b.x)

        distance = math.sqrt(math.pow(width, 2) + math.pow(height, 2))

        if distance <= a.radius + b.radius:
            # circles do intersect
            intersecting_circles.add(b)

    if len(intersecting_circles) > 0:
        all_intersecting_circles.append(intersecting_circles)

print(all_intersecting_circles)

Runtime: O((N^2)/2)

However, N^2 is the dominant complexity class and therefore we would end with O(N^2) again.
We need to calculate the distance between each tuple of circles. I don't think we can do better in this case.

The O(n^2) solution checks for intersection among each pair.
To improve it, we have various options:
- If the radius is all the same for each circle, we can put the circles in a hash map that keys to y/r and x/r (this is essentially putting r-side length squares over the 2d space. Then for the remaining n-1 circles for each of the 8 adjacent sqaures of this circle check if one circle found in this squares intersect. There are at most 8*4 circles to compare per circle which makes it O(8*4*n) = O(n)
- If the radius is not the same for each square, a two dimensional segment tree could be used on the bounding box of the circle. If a potential intersection is detected, one has to check intersection of the k points which is if the distance of the centers is less than then the sum of the two radius. This has O(n*log(n)^2) for read and insert, therefore leading to O(n*log(n)^2) performance, where as it is assumed that the number of collisions in a bounding box is not significant. One has to carefully think if worst case isn’t O(n^2) due to collisions within the bounding box of circles that still don’t overlap (e.g. if k can be a factor * n, like n/2 n/4 n/f).

//Time: O(NlogN) Space: O(N).
class Circle{
	double x;
	double y;
	double rad;
	
}

class Interval implements Comparable<Interval>{
	double start;
	double end;
	int id;
	
	public Interval(double s, double e, int idx){
		start = s;
		end = e;
		id = idx;
	}
	
	public int compareTo(Interval i){
		if(start == i.start){
			return end - i.end;
		}
		return start - i.start;
	}
}

public boolean hasIntersect(Circle[] c){

	if(c == null || c.length == 0){
		throw new IllegalArgumentException();
	}
	
	Interval[] xRange = new Interval[c.length];
	Interval[] yRange = new Interval[c.length];
	
	for(int i = 0; i < c.length; i++){
		xRange[i] = new Interval(c[i].x - c[i].r,c[i].x + c[i].r,i);
		yRange[i] = new Interval(c[i].y - c[i].r, c[i].y + c[i].r, i);
		
	}
	Arrays.sort(xRange);
	Arrays.sort(yRange);
	
	Set<String> overlaps = new HashSet<String>();
	for(int i = 1; i < xRange.length; i++){
		if(xRange[i].start <= xRange[i -1].end){
			int minId = Math.min(xRange[i-1].id, xRange[i].id);
			int maxId = Math.max(xRange[i - 1].id, xRange[i].id);
			overlaps.add(minId +", " + maxId);
		}
	}
	
	for(int i = 1; i < yRange.length; i++){
		if(yRange[i].start <= yRange[i - 1].end){
			int minId = Math.min(yRange[i -1]. id, yRange[i].id);
			int maxId = Math.max(yRange[i - 1].id, yRange[i].id);
			if(overlaps.contains(minId + ", " + maxId)){
				return true;
			}
		}
	}
	return false;
}

* build a 2D range tree from the circle centers, requires O(n log n) time (see en.wikipedia.org/wiki/Range_tree )
* for each center (x_i, y_i), find the points within the 2D range (x_i - r_i, x_i + r_i) x (y_i - r_i, y_i + r_i), requires O(log^2 n + k) time (where k is the number of points returned which can actually be n^2 in the worst case) per point. Calculate the actual Euclidean distance between the points found in the range search and the center of circle i and check whether it is less than r_i + r_other .

if the average number of points k returned in a query does not grow with n, the total time complexity is O(n log^2 n)

(the Wikipedia article also mentions that queries can even be done in O(log n + k) time for 2D trees.

O(n*log(n)) Approach is similar to quick sort. basically I am dividing the dataset into 4 sets of 1st,2nd,3rd,4th quadrant, keep the circle in all the intersecting quadrants and then recursively run it on each quadrant.

To do better than O(n^2), we either need to scan the data set multiple times in O(n) or use divide and conquer which will be O(nlog(n))

In this case, I would sort circle center by x coordinate and partition by median and use quick sort technique to find intersections in left and right. Also we need to find intersections around median as well, which in worst case may make algorithm O(n^2)

I believe that can be solved by a sweep line algorithm. However, I always find myself some homework like questions in the forum. This is one of them. I am really surprised if they ask you to write and test the code in such limited time. Maybe they only want to know if you know the method and explain it to them on a white board.

import math


class Circle(object):
    def __init__(self, x, y, r):
        super(Circle, self).__init__()
        self.x = x
        self.y = y
        self.r = r

    def get_distance(self, circle):
        return math.sqrt(math.pow(self.x - circle.x, 2) + math.pow(self.y - circle.y, 2))

    def is_intersect(self, circle):
        return self.get_distance(circle) < self.r + circle.r

    @staticmethod
    def has_intersections(list_circles):
        list_circles.sort(key=lambda a: a.x - a.r)
        sweep_intersected = []
        for circle in list_circles:
            for in_sweep in sweep_intersected:
                if circle.is_intersect(in_sweep):
                    return True
                if in_sweep.x + in_sweep.r < circle.x - circle.r:
                    sweep_intersected.remove(in_sweep)
            sweep_intersected.append(circle)
        return False


c1 = Circle(5, 5, 5)
c2 = Circle(11, 11, 5)
c3 = Circle(5.5, 10.5, 0.1)

print Circle.has_intersections([c1, c2, c3])

Project circles to x axis and find overlap there first, then check if they really overlap in 2D
Use slide window to find overlap on x. each circle can be represent as [x - radius, x+radius]
Sort them by x-radius, scan by slide window. two anchors i, j to satisify
1. circles[j][0] < circles[i][1]
2. maximize j-i

It seems that (most of) the solutions above don't take into account the fact that for two circles to *intersect* the distance between centers needs to be larger than the absolute value of the difference between the radii, and addition to being smaller than their sum.