Finding the pairs of intersecting discs I have been following this question on SO, copied below.  I put together a solution, but which is \$O(n^2)\$. In order to get a more efficient \$O(n \log n)\$ or \$O(\log n)\$ solution, I tried to sort that array, but could not get it solved hence would like to ask here how to optimize this solution to get it in less time complexity in C?


  Given an array A of N integers we draw N discs in a 2D plane,
  such that i-th disc has center in (0,i) and a radius A[i]. We
  say that the k-th disc and j-th disc intersect if they have at
  least one common point.
  
  Write a function

int number_of_disc_intersections(int[] A);

  
  which given an array A describing N discs as explained above, returns
  the number of pairs of intersecting discs. For example, given N=6 and

A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0

  
  there are 11 pairs of intersecting discs:
  
  
  0th and 1st
  0th and 2nd
  0th and 4th
  1st and 2nd
  1st and 3rd
  1st and 4th
  1st and 5th
  2nd and 3rd
  2nd and 4th
  3rd and 4th
  4th and 5th
  
  
  so the function should return 11. The function should return -1 if the
  number of intersecting pairs exceeds 10,000,000. The function may
  assume that N does not exceed 10,000,000.


C language solution:

int disc_intersecn(int *A,int N)
{
    int i,j,cnt=0;
    /*
    qsort(A,N,sizeof(A[0]),sort_fn_ascend);
    for(i=0;i&lt;(N-1);i++)
    {
        if(i+A[i] &gt; (i+1-A[i+1]))
        {
            cnt++;
        }
    }
    */

    for (i = 0; i &lt; N; i++)
    {
        for (j = i+1; j &lt; N; j++)
        {
            if (i + A[i] &gt;= j - A[j]) cnt++;
        }
    }

    return cnt;
}
Ajit,

Essentially this is a problem of 1-dimensional collision detection.

A useful tool for that is spatial-partitioning.

The book "Real-Time Collision Detection" by Christer Ericson (Morgan-Kaufmann, 2005) contains a wealth of information.  See pages 300–307 for an excellent discussion of 1-dimensional spatial hashing and pages 316—318 describing Morton keys.  The code given there is in C++ but could easily be adapted to C.

You can view a sample by clicking on "Search Inside This Book" at Amazon and then searching for "Hierarchical Grids".  The 5th link or so is page 300.

—Todd