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


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.

  • 1
    $\begingroup$ It is unclear what role the rectangles play. Are they obstacles or reservoirs of points? It may be possible for small numbers of obstacles to classify paths through the obstacles and put them in a short list, and use this for your processing. Without more clarity, I hesitate to offer further suggestions. Gerhard "Sees Some Obstructions To Answering" Paseman, 2018.06.19. $\endgroup$ – Gerhard Paseman Jun 19 '18 at 21:15
  • $\begingroup$ Thanks @GerhardPaseman, they are obstacles. I edited the post. $\endgroup$ – Chuck Newton Jun 19 '18 at 21:17
  • $\begingroup$ I suspect it will be hard. Imagine a series of m rows of 3 rectangles in each row, where the paths through a row are at distance a and b from "the left". (I am thinking of a and b as randomly chosen from the unit interval.) It strikes me that any preprocessing may need to store 2^m pieces of information. If you can solve this case efficiently, there is hope for a nice solution. Gerhard "Make All Your Obstacles Easy" Paseman, 2018.06.19. $\endgroup$ – Gerhard Paseman Jun 19 '18 at 21:42

The answer is Yes: "one can pre-process things with a higher up-front cost so as to make individual queries faster."

The Ph.D. thesis cited below shows that, with quadratic preprocessing, point-pair shortest-path queries among $n$ axis-aligned rectangles can be answered in $O(\log n)$ time. Or with $O(n^{\frac{3}{2}})$ preprocessing, queries can be answered in $O(\sqrt{n})$ time. Here the "rectilinear paths" are shortest in the $L_1$ metric, a.k.a. the Manhattan metric.

Mitra, Pinaki. "Rectilinear shortest paths among obstacles in the plane." PhD diss., Theses (School of Computing Science)/Simon Fraser University, 1995. PDF download.


It seems the later journal version of results in this thesis is this:

Mitra, Pinaki, and Subhas C. Nandy. "Efficient computation of rectilinear geodesic Voronoi neighbor in the presence of obstacles." Journal of Algorithms 28, no. 2 (1998): 315-338. Elsevier link.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.