Abstract:
Techniques are provided to determine, for a given set of possible initial needle positions, the smallest set of needles needed to guarantee a successful biopsy. Advantageously, this problem may be formulated as a “Set Covering Problem” (SCP), a well-known combinatorial optimization problem for which good approximations are known. Additionally, the present invention provides techniques to maximize the coverage of the possible initial positions for a given maximum number of k needles. This aspect of the invention may be formulated as a “Maximum k-Coverage Problem”.