Whoah, cool. I'm one of the authors of the geometric search tree paper, and we totally hadn't see that paper, but will for sure dig in! Thanks for mentioning it.