Problem: Given an array of integers where array[i] represents the radius of a circle at point (0,i)
Find the number of intersections of all the circles formed by the above array.

Example:
If given array is [2,1,3], then 3 circles would be formed whose end-points would be: [-2,2], [0,2] and [-1,5]

Solution:
An O(n^{2}) solution can be done very simply using the following properties: (Assuming R_{1} > R_{2}):

Two circles do not intersect if their centers are more than R_{1} + R_{2} distance apart.

Two circles intersect once if their centers are exactly R_{1} + R_{2} distance apart.

Two circles intersect twice if their centers are less than R_{1} + R_{2} distance apart.

Two circles intersect once if their centers are exactly R_{1} - R_{2} distance apart.

Two circles do not intersect if their centers are less than R_{1} - R_{2} distance apart.

Using the above properties, compare each circle with rest of the circles and count the number of intersections.

A possible solution to think about

Find the end-points corresponding to each circle.

Mark start points with a flag.

Sort the end-points.

Loop over the end-points.

Count the number of start-points (denoting open intervals till now).
Increment openCount by 1 if start point is encountered, else decrement by 1.

Whenever a start-point is encountered, increment intersectionCount by openCount.

Code:

import java.util.*;
public class CircleIntersections
{
// class to store one end of a circle.
// flag 'isStart' tells whether the point is start-point or end-point
public static class EndPoint
{
public int point;
public boolean isStart;
public EndPoint(int point, boolean isStart)
{
this.point = point;
this.isStart = isStart;
}
}
// comparator for class end-point
public static class EndPointCmp implements Comparator<EndPoint>
{
@Override
public int compare(EndPoint o1, EndPoint o2)
{
return o1.point - o2.point;
}
}
// Main method to find the number of intersections
public static void main(String[] args)
{
int numCircles = 5;
int[] arr = getRandomCircles(numCircles);
EndPoint[] points = getCircleEndPoints(numCircles, arr);
Arrays.sort(points, new EndPointCmp());
int startPoints = 0;
int intersections = 0;
for (int i=0; i<points.length; i++)
{
if (points[i].isStart)
{
// Whenever a new circle start point comes in, it intersects all open circles
intersections += startPoints;
startPoints++;
}
else
{
// Very Important: A circle end point need not be counted an intersection
startPoints--;
}
}
System.out.println ("Intersections = " + intersections);
}
// Each circle generates two end-points: start and end
// So return array size is twice the size of input array
static EndPoint[] getCircleEndPoints(int numCircles, int[] arr)
{
EndPoint points[] = new EndPoint[2*numCircles];
for (int i=0; i<numCircles; i++)
{
points[2*i] = new EndPoint (i - arr[i], true);
points[2*i+1] = new EndPoint (i + arr[i], false);
System.out.println ("center=" + i + ", radius=" + arr[i] + " Ends: (" + points[2*i].point + " to " + points[2*i +1].point + ")");
}
return points;
}
// Helper method to get some random circles
static int[] getRandomCircles(int numCircles)
{
int arr[] = new int[numCircles];
for (int i=0; i<numCircles; i++)
arr[i] = 1+(int)(Math.random()*numCircles*0.5);
return arr;
}
}

Sample executions:

3 circles:
center=0, radius=2 Ends: (-2 to 2)
center=1, radius=2 Ends: (-1 to 3)
center=2, radius=2 Ends: (0 to 4)
Intersections = 3
4 circles:
center=0, radius=2 Ends: (-2 to 2)
center=1, radius=2 Ends: (-1 to 3)
center=2, radius=1 Ends: (1 to 3)
center=3, radius=1 Ends: (2 to 4)
Intersections = 5
5 circles:
center=0, radius=1 Ends: (-1 to 1)
center=1, radius=2 Ends: (-1 to 3)
center=2, radius=1 Ends: (1 to 3)
center=3, radius=2 Ends: (1 to 5)
center=4, radius=1 Ends: (3 to 5)
Intersections = 5

Got a thought to share or found a bug in the code? We'd love to hear from you: