Abstract

Radiosurgery is a minimally invasive surgical procedure that uses a set of focused beams of radiation to destroy tumors. A key step in radiosurgery is to develop a treatment plan that defines the best radiation beam arrangements and time settings to destroy the target tumor without harming surrounding healthy tissues. At the core of radiosurgical treatment planning is a set of substantially non-trivial combinatorial optimization problems. However, it seems that the current practice in the medical field has mostly been on developing heuristic approaches and software, which are not necessarily based on a solid understanding and insights of the essential algorithmic nature and structures of the target problems; furthermore, an in-depth theoretical study of such problems is lacking.
This talk presents our on-going study on this research, which has resulted in an array of promising ideas and techniques in solving those computational problems arising in radiosurgical treatment planning, such as medical image segmentation, beam selection, beam shaping, and leaf sequencing problems. For example, we illustrate our solutions for the leaf sequencing problems. Leaf sequencing is a key approach to the radiation delivery in radiosurgery and radiation therapy. The previously known leaf sequencing algorithms, which are currently used in medical treatments, are all heuristics that do not guarantee any good quality of the output solutions and may run in a long time. We develop a novel unified approach for solving these problems, which leads to our leaf sequencing algorithms that are practically fast and guarantee the optimal quality of the output solutions. Our ideas include formulating the leaf sequencing problems as computing shortest paths in a directed acyclic graph with weighted edges and building the graph by computing optimal bipartite matchings on various geometric objects subject to specific medical constraints of different problems. Our implementation results show that our leaf sequencing algorithms run very fast on real medical data.