\documentclass{article}4 {% V: L6 f0 Y; j0 i, t
$ ? H( ^7 b: g) U/ O
\begin{document}3 X: v# A1 J, m2 O5 q) [$ Q9 ~2 {
z! e' R9 A6 P K2 d- E4 o\title{A Sphere-Packing Model for the Optimal Treatment Plan}2 W8 U% |; }$ N2 c2 d" Q* M( g
) y+ m" n* W/ v: m' t\author{Long Yun- |" v# M6 ?0 |8 D% L M
\and Ye Yungqing ) s4 T. w: y. }\and Wei Zhen} " I, O$ I) [( z: |4 h\address5 O" w0 I6 ^0 s. j: W
{Peking University Beijing,China} : O6 r$ m' [& e\date{}8 D8 F0 z0 A( l+ r# }6 V
\maketitle6 f, _& z0 E: @1 j+ L
: e$ d$ |8 y' `& E5 g9 V5 R\begin{abstract}( i; P9 E$ {: x& S0 e! D5 A. _
We develop a sphere-packing model for gamma knife treatment planning to & _4 A: [8 }6 ~" m2 m$ Vdetermine the number of shots of each diameter and their positions in an optimal plan.* Z& O4 z$ c" g0 d* n6 O. i
We use a heuristic approach to solve the packing problem, which is refined by: ?2 b2 s1 G) l- x# j" G9 i' L0 A+ B
simulated annealing. The criteria for an optimal plan are efficiency, conformity,fitness, and avoidance. We construct a penalty function to judge whether one packing strategy is better than the other. The number of spheres of each size is fixed, the total number of spheres has an upper bound, and critical tissue near the target is avoided.& B# {) X6 _, A( ?. x+ A* L0 F
Computer simulation shows that our algorithm fits the four requirements well # G5 r: F( t. n7 R* W- \* d* v2 |and runs faster than the traditional nonlinear approach. After detailed evaluation,we not only demonstrate the ?exibility and robustness of our algorithm but also show its wide applicability.# M% f" r; }9 t& Y* y' M. [: U
\end{abstract} . n2 G$ c: |) d5 T$ k! s2 c3 R: E# d: K2 T% n0 V% @
\section{Introduction}. U, s/ _5 k. q! n, ^
We develop an effective sphere-packing algorithm for gamma-knife treat- ) J0 y4 [. o2 c+ \9 ? q- `ment planning using a heuristic approach, optimized by simulated annealing. # a0 ^$ F* Z7 n3 K, W% G. m) x' UIn our model, we take into consideration the following basic requirements: . I4 p# L& n' {4 v\begin{enumerate} y$ B& d% b- K! x* _
\item At least 50\% shot coverage of the target volume is guaranteed. This requirement is the main standard for evaluating our algorithm, or an efficiency requirement. - E9 }0 P2 a+ c6 @3 e. r5 Q, h\item Minimize the non-target volume that is covered by a shot or by a series of delivered shots. This requirement is a conformity requirement.3 h# T9 X1 L4 j$ W9 P/ ]. A
\item Minimize the overlapped region of the delivered shots in order to avoid the hot spots as well as to economize shot usage. This is a a fitness requirement.! W4 w& C% S" j/ D/ K
\item Limit the dosage delivered to certain critical structures close to the target.Such requirements are avoidance requirements.) i5 h/ K ^) O4 I- V
\end{enumerate} S9 u$ a9 c* R5 v The traditional model for radiosurgery treatment planning via nonlinear programming assumes that the weights of the shots conform to a certain distribution,from which the construction of the objective function is possible.To avoid the complicated computation of nonlinear programming,we devise a more feasible and rapid heuristic algorithm without reducing any precision of the outcome. ( F: ~1 _( E1 B( g9 a6 y\begin{itemize)" L7 U' M! ~- L1 i. W. F+ t2 w) n
\item We consider an optimal sphere-packing plan for a given number of spheres% y ?+ s& R+ J
in each size,satisfying requirements 1-3. That is,in this step,we assume that the lesion part is far from any critical organ and try to find an optimal position for a fixed set of the spheres using the heuristic sphere-packing- T& k9 O) Y* T
algorithm. , M/ m- J, |: z7 q E$ Z& {- o- z\item We try all possible combinations of up to 15 spheres; for each,we use the above algorithm to get an optimal plan. We develop a criterion to select from the different combinations the best packing solution for our model, which is optimized by simulated annealing. + ?7 x3 f7 y2 n9 E; a" ^2 c- ?\item We consider the real situation in field practice,in which the effect of a critical organ is added.Accordingly,we modify the judgment criterion so that requirement 4 is satisfied./ V( W* V2 }5 }) O2 @) A2 s
\item Finally, to apply the above method to more general situations, we add the weights of the shots. ' y& z# j) v0 U; a1 a\end{itemize}& d# e L: L4 u4 A
Though we admit that the inherent limitations of this model due to the simplification of the problem and the restriction of the hardware capacity are unavoidable, we believe that our model has successfully solved the given problem.Our algorithm is not only fast in generating solutions but also ?exible in allowing parameter settings to solve more difficult tasks. ) Y7 `4 g" x2 d. j _& l5 Q \" K8 ?
\section{Assumption} + V4 O3 O8 u8 [* s\begin{itemize}5 L' n) O* l; e; G( t9 E
\item Shots can be represented as spheres with four different diameters: 4, 8, 14,and 18 mm. 1 |, f6 `( Y7 s, {& G\item The target volume is of moderate size with a mean spherical diameter of 35 mm (and usually less) [The Gamma Knife . . . n.d.] , f2 r1 E$ g6 o c% k- o\item The maximum number of shots allowed is 15., c* U+ \0 p0 }( Q
\item The target object is represented as a three-dimensional digital map with 100.100.100 = 1 million pixels.& E/ C M5 ^; m3 F# P9 ^& ]
\item The volume of a object is measured by the total number of pixels in it. & F* K/ N$ e! H8 c\item The dose delivered is above the lower bound of the effective level to kill the tumor.4 A& F* E8 U0 g" R* [; d& w
\end{itemize) : j, H, H- @( `$ Q2 c# j1 u6 w$ J( U) v
\section{Background Knowledge} * L$ v5 _$ K% Z3 ?" i/ l. }7 c" rGamma knife radiosurgery allows for the destruction of a brain lesions, g3 v6 |3 i" i% n; L$ S
without cutting the skin.By focusing many small beams of radiation on abnormal brain tissue,the abnormality can be destroyed while preserving the normal surrounding structures. Before the surgery, the neurosurgeon uses the digitally transformed images from the CT/MRI to outline the tumor or lesion as well as the critical structures of the surrounding brain. Then a treatment plan is devised to target the tumor. + i) F' F6 B4 ~$ z$ q" o2 Q7 QThe determination of the treatment plan varies substantially in difficulty.0 g6 a& ~+ H& u! G1 x/ r
When the tumor is large,has an irregular shape,or is close to a sensitive structure,many shots of different sizes could be needed to achieve appropriate coverage of the tumor. The treatment planning process can be very tedious and time-consuming due to the variety of con?icting objectives, and the quality of the plan produced depends heavily on the experience of the user. Therefore, a unified and automated treatment process is desired.7 y1 m0 e. c' d
In our model,we reduce the treatment planning problem to an optimal sphere-packing problem by focusing on finding the appropriate number of spheres of different sizes and their positions to achieve the efficiency, conformity,fitness,and avoidance requirements.2 D' p3 {" u0 P4 m3 T6 w8 u
\end{document}