[Solved]: Maximum non-intersecting subset of circles

Problem Detail: 

We are given a set of circles, stored by their center points in an array $A$. In particular, the center of the $i$th circle is at coordinates $(A[i].x, A[i].y)$. All the circles have radius of $k$.

I want to find a subset of circles such that no circles in this subset intersect with each other, such that this subset is as large as possible.

I'm asked to find a way to solve this using a backtracking algorithm. Rather than to do it with brute force, is there a effective way to prune some of the branches?

Asked By : RandomStudent

Answered By : HenryHey

The way I can figure out of is using 3 invariant, 1 stores selected cycles, 1 stores unselected cycles, 1 with unchecked cycles, once you add a disk $n$ from unchecked to selected, you also add the disks overlap with $n$ into the unselected and remove them from checked list, that is a way to do pruning.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35876

3.2K people like this

 Download Related Notes/Documents