3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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
    Commented Jun 19, 2018 at 21:15
  • $\begingroup$ Thanks @GerhardPaseman, they are obstacles. I edited the post. $\endgroup$
    – Chuck Newton
    Commented Jun 19, 2018 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
    Commented Jun 19, 2018 at 21:42

1 Answer 1

Reset to default
5
$\begingroup$

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.
          L_1_Shortest

          Staircase

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .