20150101
Rectilinear path problems in restricted memory setup
Publication
Publication
We study the rectilinear path problem in the presence of disjoint axis parallel rectangular obstacles in the inplace and readonly setup. The input to the problem is a set R of n axisparallel rectangular obstacles in IR2. We need to preprocess the members in R such that the following query can be answered efficiently. PathQuery(p, q): Given a pair of points p and q, report an axisparallel path from p to q avoiding the obstacles in R. In the readonly setup, we consider a restricted version of the Path Query(p, q) problem, where the objective is to check the existence of an xymonotone 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(n2/s + n log s + Ms log n) time, where Ms is the time complexity for computing the median of n elements in readonly setup using O(s) extra space. In the inplace setup, we preprocess the input rectangles in a data structure such that for any pair of query points p and q, the problem PathQuery(p, q) can be solved efficiently. The time complexities for the preprocessing and query are O(n log n) and O(n3/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 inplace data structure with same preprocessing time complexity to answer the query in O(log n) time.
Additional Metadata  

Keywords  Constant workspace, Inplace and readonly model of computation, Rectilinear path problem 
Citation 
Bhattacharya, B.K. (Binay K.), De, M. (Minati), Maheshwari, A, Nandy, S.C. (Subhas C.), & Roy, S. (Sasanka). (2015). Rectilinear path problems in restricted memory setup.
