Skip to main content
MathOverflow

Return to Answer

edited body
Source Link
Joseph O'Rourke
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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][2]][2]
It seems the later journal version of results in this thesis is this:

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

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][2]][2]
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.

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][2]][2]
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.

added 353 characters in body
Source Link
Joseph O'Rourke
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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][2]][2]  
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.

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][2]][2]

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][2]][2]  
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.

added 36 characters in body
Source Link
Joseph O'Rourke
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958

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][2]][2]

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

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][2]][2]

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][2]][2]
added 200 characters in body
Source Link
Joseph O'Rourke
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958
Source Link
Joseph O'Rourke
Joseph O'Rourke
  • 150.8k
  • 36
  • 358
  • 958