Thomas Kalinowski
The algorithmic complexity of the minimization of the number of segments in multileaf collimator field segmentation
Preprint series: Preprints aus dem Fachbereich Mathematik, Universität Rostock

MSC:

92C50 Medical applications (general)

90C60 Abstract computational complexity for mathematical programming problems, See also {68Q25}

Abstract: Intensity maps are nonnegative matrices describing the
intensity modulation of beams in radiotherapy. In order to
use a multileaf collimator in the static mode for the
realization of the intensity modulation one has to
determine a segmentation, i.e. a representation of an
intensity map as a positive combination of special matrices
corresponding to fixed positions of the multileaf collimator,
called segments. We consider the problem to construct
segmentations with the minimal total number of monitor units
and the minimal number of segments. Neglecting machine--
dependent constraints like the interleaf collision constraint
and assuming that the entries of the intensity map are
bounded by a constant, we prove that a segmentation with
minimal number of segments under the condition that the
number of monitor units is minimal, can be determined in
time polynomial in the matrix dimensions. The results of
our algorithm are compared with Engel's \cite{Eng02}
heuristic for the reduction of the number of segments.
Keywords: leaf sequencing, radiation therapy optimization, intensity modulation, multileaf collimator, IMRT