patternMinor
Minimum circles to cover a set of points and avoid another set of points
Viewed 0 times
pointsminimumcirclesavoidanotherandcoverset
Problem
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?
circles can have arbitrary radius
any thoughts about the difficulty of this problem? any thoughts on non trivial exact algorithms?
Solution
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!
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!
Context
StackExchange Computer Science Q#120673, answer score: 3
Revisions (0)
No revisions yet.