A gamma dose distribution evaluation technique using the k-d tree for nearest neighbor searching.
OBJECTIVE
The authors propose an algorithm based on the k-d tree for nearest neighbor searching to improve the gamma calculation time for 2D and 3D dose distributions.


METHODS
The gamma calculation method has been widely used for comparisons of dose distributions in clinical treatment plans and quality assurances. By specifying the acceptable dose and distance-to-agreement criteria, the method provides quantitative measurement of the agreement between the reference and evaluation dose distributions. The gamma value indicates the acceptability. In regions where gamma < or = 1, the predefined criterion is satisfied and thus the agreement is acceptable; otherwise, the agreement fails. Although the concept of the method is not complicated and a quick naïve implementation is straightforward, an efficient and robust implementation is not trivial. Recent algorithms based on exhaustive searching within a maximum radius, the geometric Euclidean distance, and the table lookup method have been proposed to improve the computational time for multidimensional dose distributions. Motivated by the fact that the least searching time for finding a nearest neighbor can be an O (log N) operation with a k-d tree, where N is the total number of the dose points, the authors propose an algorithm based on the k-d tree for the gamma evaluation in this work.


RESULTS
In the experiment, the authors found that the average k-d tree construction time per reference point is O (log N), while the nearest neighbor searching time per evaluation point is proportional to O (N(1/k), where k is between 2 and 3 for two-dimensional and three-dimensional dose distributions, respectively.


CONCLUSIONS
Comparing with other algorithms such as exhaustive search and sorted list O (N), the k-d tree algorithm for gamma evaluation is much more efficient.
ICT Radiotherapy, Livingston, New Jersey 07039, USA. jiankui.yuan@gmail.com
Jiankui
J
Yuan
Weimin
W
Chen
D000465:Algorithms; D011829:Radiation Dosage; D013997:Time Factors