Dave, If you look at the branch xroute-nlogn, there's some code to update xroutes in n logn time. It's almost completely untested. If you've got time, I'd be grateful if you could have a look.