Companion website of "Towards unlocking the full potential of Multileaf Collimators" by G. Blin, P. Morel, R. Rizzi and S. Vialette. Proceedings of SOFSEM 2014

Companion website of "Towards unlocking the full potential of Multileaf Collimators" by G. Blin, P. Morel, R. Rizzi and S. Vialette. Proceedings of SOFSEM 2014

Illustration of the matrix M

Illustration of the rounding technique

Let us present the rounding technique for a single row - say the k^th. Considering all the corresponding variables {H^k_ij| 1 ≤ i ≤ j ≤ m }, one can represent each non-null variable H^k_ij by an interval [i,j] over the real line on [1,m] weighted by H^k_ij.

Let us transform this set of intervals I into a set I', where given any pair of intervals either one is included into the other or they are disjoint. To do so, we process I with the following algorithm. While there exists two intervals [i,j] and [k,l] with respective weights w₁ and w₂ such that i<k<j<l (i.e. crossing) remove [i,j] and [k,l] from I and add [i,k-1], [k,j] and [j+1,l] with respective weights w₁, w₁+w₂ and w₂.

As an example, considering Figure 3, given intervals [1,9] and [3,11], it will result in intervals [1,2], [3,9] and [10,11] with respectively weights H^k_1,9, H^k_1,9+H^k_3,11 and H^k_3,11. Now that all intervals are nested or independent, while there exists three intervals [x,y], [i,j] and [k,l] with respective weights w₁, w₂ and w₃ such that x≤ i<j ≤ k<l≤ y, if j<k then remove [x,y] from I and add [x,j] and [j+1,y] both weighted by w₁; otherwise (j=k) remove [i,j] and [k,l] from I and if w₂< w₃ then add [i,l] and [k,l] with respective weights w₂ and w₃-w₂; otherwise add [i,l] and [i,j] with respective weights w₃ and w₂-w₃.

As an example, given intervals [3,9], [4,7] and [9,9], it will result in intervals [3,7], [8,9], [4,7] and [9,9]. Moreover given two copies of an interval [i,j] with respective weights w₁ and w₂, remove them and add an interval [i,j] with weight w₁+w₂. As an example, copies of intervals [1,2], [3,7] and [8,9] have been merged.

MOD Hardness instance generator

This form allows you to build a sample instance for the hardness proof of "Towards unlocking the full potential of Multileaf Collimators" by G. Blin, P. Morel, R. Rizzi and S. Vialette.