A Heuristic Approach for Partial Covering Polyhedral Domains by Spheres

A non-standard sphere placement problem arising in optimizing treatment planning in radiosurgery is considered. A methodology for positioning spheres (representing radiation shots) within a 3D domain corresponding to a tumor is proposed. The domain is described as a union of disjoint convex polytopes. Spheres can have a limited overlap to avoid overdosing. This problem is referred to as a partial covering problem. The objective is to maximize the filling coefficient for the tumor regions subject to sphere overlapping constraints while monitoring underdosing. A new heuristic approach is proposed that employs an iterative optimization procedure for arrangement spheres of predetermined sizes combined with the smart feasible starting point algorithm. Numerical examples are presented to illustrate the approach.