New Algorithm for Field Splitting in Radiation Therapy

Xiaodong Wu; Xin Dou; John Bayouth; John Buatti

doi:10.1007/978-3-540-77120-3_60

Back

Book chapter

New Algorithm for Field Splitting in Radiation Therapy

Xiaodong Wu, Xin Dou, John Bayouth and John Buatti

Algorithms and Computation, pp.692-703

Lecture Notes in Computer Science, Springer Berlin Heidelberg

2007

DOI: 10.1007/978-3-540-77120-3_60

View Online

Abstract

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.

Polygonal Path

Multileaf Collimator

Linear Time Algorithm

Optimal Decomposition

Directed Acyclic Graph

Details

Title: Subtitle: New Algorithm for Field Splitting in Radiation Therapy
Creators: Xiaodong Wu - Department of Radiation Oncology, University of Iowa, Iowa City, IA 52246, USA
Xin Dou - Department of Electrical and Computer Engineering,
John Bayouth - Department of Radiation Oncology, University of Iowa, Iowa City, IA 52246, USA
John Buatti - Department of Radiation Oncology, University of Iowa, Iowa City, IA 52246, USA
Resource Type: Book chapter
Publication Details: Algorithms and Computation, pp.692-703
Publisher: Springer Berlin Heidelberg; Berlin, Heidelberg
Series: Lecture Notes in Computer Science
DOI: 10.1007/978-3-540-77120-3_60
eISSN: 1611-3349
ISSN: 0302-9743
Language: English
Date published: 2007
Academic Unit: Electrical and Computer Engineering; Radiation Oncology; Neurosurgery; Otolaryngology
Record Identifier: 9984047662402771

Metrics

21 Record Views