Rectilinear Path Problems in Restricted Memory Setup

We study the

rectilinear path problem

in the presence of disjoint axis parallel rectangular obstacles in the

in-place

and

read-only

setup. The input to the problem is a set

$\cal R$

of

n

axis-parallel rectangular obstacles in

$I\!\!R^2$

. We need to preprocess the members in

$\cal R$

such that the following query can be answered efficiently.

Path-Query

(

p

,

q

): Given a pair of points

p

and

q

, report an axis-parallel path from

p

to

q

avoiding the obstacles in

$\cal R$

.

In the

read-only

setup, we consider a restricted version of the

Path-Query

(

p

,

q

) problem, where the objective is to check the existence of an

xy

-monotone path between the given pair of points

p

and

q

avoiding the obstacles, and report it if such a path exists. Given

O

(

s

) extra space, the problem can be solved in

$O(\frac{n^2}{s}+n\log s+ M_s\log n)$

time, where

M

s

is the time complexity for computing the median of

n

elements in read-only setup using

O

(

s

) extra space.

In the

in-place

setup, we preprocess the input rectangles in a data structure such that for any pair of query points

p

and

q

, the problem

Path-Query

(

p

,

q

) can be solved efficiently. The time complexities for the preprocessing and query are

O

(

n

log

n

) and

O

(

n

3/4

 + 

χ

) respectively, where

χ

is the number of links (bends) in the path. The extra space requirement for both preprocessing and query answering are

O

(1). We also show that among a set of unit square obstacles, there always exists a path of

O

(log

n

) links between a pair of query points. Here, we use a different in-place data structure with same preprocessing time complexity to answer the query in

O

(log

n

) time.