New algorithm for field splitting in radiation therapy

In this paper, we study an interesting geometric partition problem, called optimal field splitting, which arises in Intensity-Modulated Radiation Therapy (IMRT), In current clinical practice, a multi-leaf collimator (MLC) is used to deliver the prescribed intensity maps (IMs). However, the maximum leaf spread of an MLC may require to split a large intensity map into several overlapping sub-IMs. We develop the first optimal linear time algorithm for solving the field splitting problem while minimizing the total complexity of the resulting sub-IMs. Meanwhile, our algorithm strives to minimize the maximum beam-on time of those sub-IMs. Our basic idea is to formulate the field splitting problem as computing a shortest path in a directed acyclic graph, with a special "layered" structure. The edge weights of the graph satisfy the Monge property, which enables us to speed up the algorithm to optimal linear time. To minimize the maximum beam-on time of the resulting sub-IMs, we consider an interesting min-max slope path problem in a monotone polygon which is solvable in linear time. The min-max slope path problem is of its own interest.