There are some things to try which require modifying kdtree.hh and the downset implementations based on it.
kdtree.hh should be parameterized to determine whether the median is used as pivot or the vector currently in the middle is used (cheaper, but does not guarantee balancedness). In the latter case, maybe one can even disable the tricks introduced for the order to be strict.
kdtree.hh should also allow for a height parameter that determines when the tree stops. This means leaves are no longer vectors in general, rather they are sets of vectors. For this, there is probably another parameter to be introduced for the implementation of the downset at the leaves.
The downset implementations using kdtree.hh have to be updated accordingly.
There are some things to try which require modifying
kdtree.hhand the downset implementations based on it.kdtree.hhshould be parameterized to determine whether the median is used as pivot or the vector currently in the middle is used (cheaper, but does not guarantee balancedness). In the latter case, maybe one can even disable the tricks introduced for the order to be strict.kdtree.hhshould also allow for aheightparameter that determines when the tree stops. This means leaves are no longer vectors in general, rather they are sets of vectors. For this, there is probably another parameter to be introduced for the implementation of the downset at the leaves.kdtree.hhhave to be updated accordingly.