ex_hausted's blog

By ex_hausted, history, 5 months ago, In English

Can someone please explain how to solve this question ?

Given a continuous plane, there are N circles each having coordinate like (cix, ciy) and radius ri. Given a rectangle( the rectangle has length parallel to x-axis and breadth parallel to y-axis) having top-left corner as P1(p1x, p1y) and bottom-right corner as P2(p2x, p2y). Tell if it is possible( true or false ) to travel from P1 to P2 without touching or crossing the circles while being inside the rectangle.

NOTES:

  • The coordinates are NOT necessarily integer coordinates.
  • The trajectory of travel from P1 to P2 may not necessarily be a straight line, it can be anything (think of it like a river).
 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ex_hausted (previous revision, new revision, compare).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Give us a link to the problem, and/or ranges for coordinates, i might have a way to solve this, or at least help you a little bit.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, this was an interview problem, don't have a link. Also, coordinates can be anything that can be solved in general, no special coordinates.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Im really sorry then, but this is full of questions for ongoing interviews. Can't help you.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you are referring to this task on interviewbit. It can be solved using BFS.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The question in this post doesn't necessarily have integer coordinates, it is a continuous plane. Also, the interviewbit question assumes integer coordinates, have defined directions(8 directions) to travel to, here the trajectory of travel from P1 to P2 can be anything.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

This is a very interesting problem. I believe I know of a solution, but it depends on how large the constraint for N is. This solution should run O(N^2). First we build a graph on the circles, there is an edge between two circles if they intersect (the distance between their centers is no more than the sum of their radii). Now we perform BFS/DFS on the circles. If we are able to connect the top of the rectangle to the bottom of the rectangle or top to left or left to right or bottom to right, then the answer should be false. Otherwise the answer is true.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had the same solution in mind but do you know if there's any divide-and-conquer/line-sweep trick to bring it down from N^2?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Normally, I would try something like that, but it seems quite difficult (maybe even impossible) in this case because of two issues:

      1. We are working with circles
      2. We are not working with integer coordinates

      That being said, there may be ways to optimize my naive BFS/DFS approach since a lot of the N^2 edges will be redundant.

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Its simple disjoint set union, merge Circle or just those points basically which interset that can be possible hindrance to path, if there is hindrance then it is not possible else it's possible,
Hindrance is of the form top-right, top-bottom, bottom-right, bottom left
Total complexity will be O(N^2) (also O(N log N) using Delaunay triangulation not needed tho) as you can merge in incremental order to skip, parent merging.
This is based on the assumption that when circle intersect projection of those diameter will block the whole path