Intensity-modulated radiation therapy (IMRT) is a modern cancer treatment technique aiming to deliver a prescribed conformal radiation dose to a target tumor while sparing the surrounding normal tissues and critical structures. The prescribed radiation dose is specified by intensity maps (IM).

In this thesis, we study a set of combinatorial and geometric problems that arise in IMRT planning and delivery: (1) the 3-D static leaf sequencing (SLS) problem, whose goal is to deliver the prescribed IMs in the minimum amount of time; (2) the 3-D static leaf sequencing with error control problem, which aims to deliver the prescribed IMs in the minimum amount of time subject to the contraint that no unnecessary machine delivery error is introduced; (3) the field splitting problems, which seek to split a large width, undeliverable IM into several deliverable sub-IMs of widths no larger than a given threshold value such that the total beam-on time during delivery is minimized; (4) the shape rectangularization problems, which are useful in simplifying a complicated continuous dose distribution into a deliverable discrete IM; (5) the coupled path planning problems, which are directly related to dynamic leaf sequencing and single-arc dose painting, an emerging IMRT delivery technique.

Known algorithms for the above problems, both in commercial planning systems and in medical literature, either are heuristics that do not provide any quality guarantee of the solutions, or could handle only very special cases. In this thesis, we present new efficient algorithms for these problems that guarantee the optimal quality of the solutions. Our main ideas are to exploit the underlying geometric and combinatorial properties of the problems and transform them into graph problems such as shortest paths, optimal matchings, maximum flows, multicommodity demand flows, or linear programming problems.

We have implemented most of the proposed algorithms and experimented with them using real medical data. Compared with commercial treatment planning systems and well-known algorithms in medical literature, our algorithms produce treatment plans of much better quality. Some of the software that we have developed has been clinically used for treating cancer patients at two hospitals in Maryland.