0

One problem states:

Given two sets $A_1$ and $A_2$ with $n_1$ and $n_2$ points respectively, design an algorithm to compute (if it exists) a disk containing all the points in $A_1$ and none in $A_2$.

My idea is to calculate the minimum spanning circle of both sets (that takes linear time) and see if they intersect (I don't know the running time of this. Maybe you can draw a segment between both centers and see which circle comes first if you see it form the left). If they do, we don't have a solution.

Is this idea correct? If so, it is the best one? If not, how can I do it?

Lecter
  • 449
  • Doesn't such a disk necessarily contain the minimum spanning circle of $A_1$? Can't you just compute the minimum spanning circle $C$ of $A_1$ and test each of the points in $A_2$ to see if it lies in $C$? – saulspatz Oct 19 '19 at 17:08
  • @saulspatz And which is the time complexity of the second part of what you are saying? Also, probably it's easy to compute the disk than the minimum spanning circle (in a sense of time). – Lecter Oct 19 '19 at 17:58
  • I don't understand what you are saying. You said you want to start by computing two minimum spanning circles; I say you only need to compute one, and you say that takes too much time? – saulspatz Oct 19 '19 at 18:00
  • @saulspatz No, no... I'm just trying to follow your idea as I see it much faster. I was just asking about the time complexity of your idea. – Lecter Oct 19 '19 at 19:47
  • 1
    Well, the second part should be linear in $n_2$ If you know the center and radius of the minimum spanning circle you just have to test if the square of the distance from a given point to the center is less than the square of the radius. – saulspatz Oct 19 '19 at 20:40

0 Answers0