2
\$\begingroup\$

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:

  1. 0th and 1st
  2. 0th and 2nd
  3. 0th and 4th
  4. 1st and 2nd
  5. 1st and 3rd
  6. 1st and 4th
  7. 1st and 5th
  8. 2nd and 3rd
  9. 2nd and 4th
  10. 3rd and 4th
  11. 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<(N-1);i++)
    {
        if(i+A[i] > (i+1-A[i+1]))
        {
            cnt++;
        }
    }
    */

    for (i = 0; i < N; i++)
    {
        for (j = i+1; j < N; j++)
        {
            if (i + A[i] >= j - A[j]) cnt++;
        }
    }

    return cnt;
}
\$\endgroup\$
  • \$\begingroup\$ Seeing as that question already has an answer explaining the method, why are you asking here? \$\endgroup\$ – Winston Ewert Jan 29 '12 at 15:50
  • \$\begingroup\$ @WinstonEwert - Because I am trying to solve it in C , not in C#, Python, Java which are mentioned, and i did not get the explanation. \$\endgroup\$ – goldenmean Jan 29 '12 at 16:01
  • \$\begingroup\$ He's also looking for an improved solution (meaning faster, more efficient). His example solution was simply to illustrate an O(N²) solution. Clearly there is room for improvement if a fancier solution is available. \$\endgroup\$ – Todd Lehman Jan 29 '12 at 16:11
  • \$\begingroup\$ What do you think somebody is going to give you here besides a description of the same algorithm? \$\endgroup\$ – Winston Ewert Jan 29 '12 at 18:37
  • \$\begingroup\$ @ToddLehman, yes. But his link already describes the fancier solution. \$\endgroup\$ – Winston Ewert Jan 29 '12 at 18:37
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.