The Algorithm for computing the SIG in a plane
Input:A set of points in the plane.
Output:A connected or disconnected graph G. This is the Spheres-of-Influence Graph.
The animated image below demonstrates the above algorithm.
The dotted lines indicate the shortest distance point from each of the individual points, Then the circles are drawn centered on the points and raidus equal to the distance to its nearest neighbor. The intersections of the circles are found and then the corresponding points are joined by an edge.
The SIG of a set of points can be found using the brute force approach as described above. There is a faster way of computing the SIG as well. The time requirements of both these techniques are discussed in some detail below.
The Bentley and Ottmann algorithm finds the intersections between line segments by using a sweep line technique. A horizontal line L is swept on the set of line segments S. Let us assume that x= si sj be the intersection between two line segments, si and sj. Look at the figure below.
Just before the sweepline L reaches the intersection point x, we can see that si and sj are adjacent on L. Therefore, it is only necessary to compute intersections between pairs of line segments that are adjacent on L. Of course, some of these adjacent lines do not actually intersect (for example sh and si) but that penalty is small enough to be insignificant in computing the total running time. Bentley and Ottmann showed that this algorithm can find intersections between pairs of line segments in O((n+k)logn) time, where k is the total number of intersections. Chazelle and Edelsbrunner reduced the running time to O(nlogn+k).
Then we label each arc to indicate from which circle it comes from. Thus, each circle will have four arcs each. These arcs each are a quarter of the perimeter-length of the original circle. But most importantly, these are monotonic in both the X and Y directions. Which means, we can apply the Bentley and Ottmann algorithm to find intersections between them. The slight modification we have to make is this: when we find an intersection, we have to check whether or not they belong to the same circle (by checking the corresponding labels). If so, then we ignore the result. Otherwise we have an intersection between two circles. Therefore, this will yield an overall complexity of O(nlogn) for finding the intersection between circles. This approach was used by Hisham ElGindy to find the SIG in O(nlogn) time, as mentioned in .