Jarjit_sigh's blog

Help with geometry problem
By Jarjit_sigh, history, 5 years ago, In English

Given a set of circles on a Cartesian plane, there are no 2 circles sharing a point. For each circle we want to find the smallest circle that contains it, or report that there is none.

I tried many solutions that works with rectangles, but none can be modified to work with circles. Any suggestions? :(

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

»
5 years ago, # |
← Rev. 4   Vote: I like it +22 Vote: I do not like it

sweepline by x-coordinate. for each circle you keep the interval of y-coordinate that it covers. since no pair of circles intersects, they only swap their relative position when sorted when either of them leave or enter the sweepline, which you can just remove/add them. thus you can maintain a set/treap of the order of the intervals in $$$O(n*\log_2n)$$$ time.

granted it would not be the most elegant implementation ever, but it *might works.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When considering the line x = a, you can split the circles that cross through this line into 2 halves: up and down. So you can sort these semicircles as a bracker sequence. For finding the smallest circle that contains the circle c, you can find the semicircle s greater than or equal to up semicircle of c by lower_bound, the result is s or result of s.

→ Reply