I am looking for the fastest possible algorithm for solving the following problem: I am given a collection of disjoint axis-aligned rectangles in the plane, and I need to pre-process these rectangles so that, given any two arbitrary points $x_1,x_2$, I can quickly compute the length (with respect to the Manhattan norm) of the shortest path between $x_1$ and $x_2$. The paper

https://link.springer.com/article/10.1007/BF01758836

shows that this can be done in in $O(n\log^2 n)$ for a particular pair of points, but I'm curious if one can pre-process things with a higher up-front cost so as to make individual queries faster.

I am looking for the fastest possible algorithm for solving the following problem: I am given a collection of disjoint axis-aligned rectangles in the plane, and I need to pre-process these rectangles so that, given any two arbitrary points $x_1,x_2$, I can quickly compute the length (with respect to the Manhattan norm) of the shortest path between $x_1$ and $x_2$ that avoids the rectangles. The paper

https://link.springer.com/article/10.1007/BF01758836

shows that this can be done in in $O(n\log^2 n)$ for a particular pair of points, but I'm curious if one can pre-process things with a higher up-front cost so as to make individual queries faster.