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$. 143
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. 143