A gamma dose distribution evaluation technique using the k-d tree for nearest neighbor searching

Area of Science:

• Medical Physics
• Computational Science

Background:

• Gamma calculation is crucial for comparing dose distributions in radiation therapy.
• Efficient gamma evaluation is essential for clinical treatment plan quality assurance.
• Existing methods face computational challenges with complex dose distributions.

Purpose of the Study:

• To develop a novel algorithm for faster gamma evaluation in 2D and 3D dose distributions.
• To leverage k-d tree data structures for optimizing nearest neighbor searching.
• To enhance the efficiency of gamma calculation in radiation therapy quality assurance.

Main Methods:

• An algorithm utilizing k-d trees for nearest neighbor searching was proposed.
• The k-d tree approach aims to reduce the computational time for gamma evaluation.
• This method was compared against traditional exhaustive search and sorted list algorithms.

Main Results:

• K-d tree construction time per reference point averages O(log N).
• Nearest neighbor searching time per evaluation point is O(N^(1/k)), with k=2 for 2D and k=3 for 3D.
• The k-d tree algorithm demonstrates superior efficiency over O(N) methods.

Conclusions:

• The k-d tree algorithm offers a significant improvement in computational efficiency for gamma evaluation.
• This method provides a faster and more robust solution for comparing dose distributions.
• The proposed algorithm is highly efficient for quality assurance in radiation therapy.