Brachytherapy Seed Localization Using Geometric and Linear Programming Techniques

We propose an optimization algorithm to solve the brachytherapy seed localization problem in prostate brachytherapy. Our algorithm is based on novel geometric approaches to exploit the special structure of the problem and relies on a number of key observations which help us formulate the optimization problem as a minimization integer program (IP). Our IP model precisely defines the feasibility polyhedron for this problem using a polynomial number of half-spaces; the solution to its corresponding linear program is rounded to yield an integral solution to our task of determining correspondences between seeds in multiple projection images. The algorithm is efficient in theory as well as in practice and performs well on simulation data (~98% accuracy) and real X-ray images (~95% accuracy). We present in detail the underlying ideas and an extensive set of performance evaluations based on our implementation.