Common algorithms for creating bounding-volume-hierarchies (BVH) rely on grouping primitives together that are not necessarily adjacent in memory. This is either done by rearranging the primitives directly or using an index which is then sorted. What if we are not allowed to change the order of the primitives? More formally:

Let $P={p_1, p_2, …, p_k}$ be an ordered set of primitives. A BVH can be constructed by splitting the set of indices $I={1,2,…,k}$ into two subsets $I_l$ and $I_r$ so that $I_lcap I_r=emptyset$ and $I_l cup I_r=I$. $I_l$ and $I_r$ correspond to the indices of all primitives in the left and right child node of the root node. This procedure then repeats recursively for $I_l$ and $I_r$ and so on.

Now add the additional constraint that $forall i in I_l forall j in I_r(i<j)$. This prevents rearranging and makes the problem quite interesting in my opinion.

The quality of the best achievable BVH without rearranging primitives depends heavily on the initial order of the primitives. Instead of choosing a spatial split position, for example using the surface area heuristic, we are restricted to choosing a *split index* instead. My guess is that this would make agglomerative clustering algorithms much more attractive, as only adjacent primitives can be clustered together, not arbitrary pairs of primitives.

Has this problem been studied in the literature before?