I think searchsorted is necessary for the code to work with any type of rbins (logarithmic space or whatever the user wants)
Regarding the question on balltree, the calls to balltree and inrange take about 6.813 seconds, when using 100000 objects, whereas the full code takes about 7 seconds. Therefore the answer is yes, most of the time is spent in balltree. Do you know of any alternatives I could use to efficiently extract all objects within a maximum distance for every object?