rahul_1234's blog

Interview Question
By rahul_1234, history, 8 years ago, In English

Given 'n' circles (each defined by center and radius) Write an algorithm to detect if given circles intersect with any other circles in the same plane

Better than O(n^2) complexity

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If I got the problem correctly, for each circle you just need to loop though all others and compare the distance between two centers versus the sum of two radiuses. Two circles intersect if the former is not greater than the latter.

The time complexity for the above approach would be O(n^2) ______

Updated 1: Sorry the time complexity is not good enough

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yes, but a better approach O(NlogN) is reqd.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it +21 Vote: I do not like it

      Sweep line, make a vertical line sweep from x=-inf to x=+inf, whenever it touch a circle from left insert the Y coordinates of its center to a std::set and check if this circle intersects with the two circles which become immediately before and after this circle in the std::set, whenever the line touches from a circle from right remove that circle from set now check if the two circles which was before and after the removed circle in the std::set intersect with each other.

      UPD: I considered that intersecting of two circles means having a common area

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Can u explain using some example.

        A brief example would be very useful.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Give me an example you want me to explain

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Any example of choice where I can visualise the algo?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              ← Rev. 2   Vote: I like it +3 Vote: I do not like it

              Maybe 4 circles like this Pic where

              1 intersects 2, 3, 4

              2 intersects 3, 4

              3 intersects 4

              or any other to get intuitive explanation.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                if you have 4 circles such that all pairs intersect with each other then here's how the algorithm will work:

                the sweeping line will move until it touches the first circle from the left, you will insert its Y coordinates to std::set now the line will continue sweeping until it touches another circle from left and you will add its Y coordinates to std::set, since there was only one circle in the std::set the newly added circle will come either after or before it so you have to check if those two circles intersect and they indeed intersect because all circles intersect with each other so you just return that there's intersection and terminate the algorithm.

                → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              This link may help you

              → Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Do I have to say whether there are 2 circles that intersect or the pairs of circles that intersect?

→ Reply