Points are in 2d euclidean space. Given a set of n points, A, and a set of m points, B, what is the minimally sized set of circles such that this set of circles covers all points in A and no point in B is covered by a circle?
circles can have arbitrary radius
any thoughts about the difficulty of this problem? any thoughts on non trivial exact algorithms?
If $B$ is empty, just pick a single circle. Otherwise, here's a way to turn this continuous problem into a discrete (but still probably hard) problem:
Lemma: There exists an optimal solution in which every circle falls into one of the following cases:
Proof sketch: Suppose we have an optimal solution. For any circle with no $A$-points on its boundary, shrink it (keeping the centre in the same position) until it does: Notice that shrinking never causes a point that was outside the circle to move inside it, so this never causes a $B$-point to become covered. Do this for all circles, until all circles have at least one $A$-point on their boundary. If that is the only $A$-point in the circle, shrink that circle all the way down to diameter 0 and centre it at that point.
Second, for any circle that has only one $A$-point on its boundary but at least one other $A$-point inside it, "pull-shrink" it towards the boundary point until at least one more $A$-point lies on its boundary. By "pull-shrink" I mean: Keep that boundary $A$-point on the boundary, and move the circle centre some distance $x$ along the straight line towards it, thereby also reducing the circle's radius by $x$. Pull-shrinking also never causes a point that was outside the circle to move inside it. Think of lying a cylinder on the ground so that it could roll, and putting a smaller-diameter cylinder inside it: the smaller cylinder lies completely inside the larger one, touching it only at the very bottom point.
Finally, "puff out" each circle until either an $A$-point inside it almost escapes (lies on the boundary), or a $B$-point outside it almost touches the boundary, whichever happens first. By "puff out" I mean: Keep the 2 boundary $A$-points on the boundary, and move the circle centre away from them along their perpendicular bisector, causing it to enlarge. Unlike shrinking and pull-shrinking, puffing out can cause points that were inside the circle to move outside, and vice versa. That's why we need a more flexible stopping condition. (For this process to terminate, it may actually be necessary to move the circle centre in the opposite direction, which initially shrinks it: This is necessary if there are no $B$-points in the half-plane defined by the line connecting the two boundary $A$-points and containing the circle centre. Since we have assumed $|B| \ge 1$, at least one of the two half-planes contains a $B$-point, so at least one of the two movement directions will cause the circle to eventually get within $\epsilon$ of a $B$-point, which is all that matters for this proof.)
Starting from an arbitrary optimal solution, after performing these steps, we have constructed a same-size (i.e., optimal) solution that still covers all $A$-points, avoids all $B$-points, and in which each circle either has diameter zero, or has at least 2 $A$-points on its boundary, in addition to either a third boundary $A$-point or a $B$-point just outside its boundary. What this means is that it suffices to consider only solutions in which each circle has this property.
Since any 3 non-collinear points lie on the boundary of exactly 1 circle, we need only consider a finite-size set of circles to choose from:
Of course, you can also get rid of any circle whose $A$-points are completely contained by some other valid circle, and doing so should speed things up.
To solve the problem, generate these $O(n^3)$ circles and solve a Set Cover problem in which the set of items to be covered is $A$, and each circle contributes a set, namely the set of $A$-points that it covers.
It may be that the Euclidean structure in the problem means that some asymptotically faster algorithm can be used than a general Set Cover solver.
The following algorithm will find some set of circles, containing all the points in the set $A$ except all the points in the set $B$. This solution might be not optimal (please see the @j_random_hacker counterexample in comments), and it's unclear how close this solution will be to the optimal one. The time complexity of this algorithm is exponential, cause it needs the Set Cover Problem solution as one of its steps.
Step 1. Build Voronoi Diagram of the set $B$. This diagram will consist of cells, nodes, line segments and rays. Each node will correspond to (at least) three points from the set $B$, and each ray will correspond to exactly two points from the set $B$.
Step 2. For each Voronoi node construct a maximal empty open disk with center in this node. These disks will have (at least) three points from the set $B$ on their boundary, and they won't contain any points from the set $B$. The number of such disks will be $\Theta(|B|)$.
Step 3. For each Voronoi ray construct a maximal empty open disk with center at this ray and infinitely large radius - it'll be actually a halfplane, corresponding to two points from the convex hull of the set $B$. These "disks" will have exactly two points from the set $B$ on their boundary, and they won't contain any points from the set $B$. The number of such "disks" will be $\Theta(|B|)$.
Step 4. For each point from the set $A$ find all disks, constructed above, containing this point. Each such point may belong to more than one disk, and each disk may contain any number of points from zero to $|A|$. Find a minimal subset of the set of all disks, which contains all the points from the set $A$. This is the classic Set Cover Problem, which is NP-complete (it's tempting to try to use geometric nature of this sub-problem to accelerate the search, however it won't be possible - please see the Geometric Set Cover Problem page for more details).
I'm thankful to @DiscreteLizard for pointing my error out in the previous version of this answer, and for suggesting the term "disk", which looks more adequate than the "circle".
I'd call this problem a "Bomber Problem" - we try to use a minimal number of bombs to strike all needed locations except some friendly ones. Sorry for militaristic jargon!
The following randomized incremental algorithm finds a set of disks, containing all the points from the set $A$ except all the points from the set $B$, in polynomial time. It's unclear, how close this set of disks will be to the optimal solution.
The algorithm maintains a disk set, containing a subset of the set $A$ and not containing any points from the set $B$. Points from the set $A$ are inserted into the disk set one by one. The disk set can change at each step. The algorithm ends after all the points from the set $A$ are inserted into the disk set.
Step 1. Randomly choose a point $p_1 \in A$ and create a disk $D_1$ with center in the point $p_1$ and zero radius. Create a disk set $S=\{D_1\}$.
Step $i$ for $i \gt 1$. The previously constructed disk set $S=\{D_1,\dots,D_k\}$ contains points $\{p_1,\dots,p_{i-1}\} \subset A$ and doesn't contain any points from the set $B$. Randomly choose a point $p_i \in A \setminus \{p_1,\dots,p_{i-1}\}$ and perform following operations.
If the point $p_i$ is contained in some disk from the set $S$, then this set isn't changed - step $i$ is done.
Otherwise randomly scan disks from the set $S$ trying to find an expandable disk - a disk $D$, which can be expanded to contain all the points it contained previously plus the new point $p_i$. This expanded disk can be constructed easily, however to be expandable it must meet additional condition - this disk must not contain any points from the set $B$.
If such expandable disk $D^*$ is found, replace the disk $D$ by the disk $D^*$ in the set $S$ - step $i$ is done. If an expandable disk is not found, create a new disk with center in the point $p_i$ and zero radius. Add this disk to the set $S$.
Each step of this algorithm will need to scan at most $n$ disks, and for each expanded disk - verify its intersection with all the $m$ points from the set $B$. So, the running time of this algorithm is obviously $O(n^2m)$. This estimate can be improved using more sophisticated data structures for sets $S$ and $B$.
The algorithm can be generalized to work with any types of obstacles instead of isolated points - segments, polygons etc.
