Name
Abstract | ||
|---|---|---|
We study the rectilinear path problem in the presence of disjoint axis parallel rectangular obstacles in the read-only and in-place setup. The input to the problem is a set R of n axis-parallel rectangular obstacles in R2. The objective is to answer the following query 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 R. In the read-only setup, we show that Path-Query(p,q) problem can be solved in O(n2s+nlogs) time using O(s) extra space. We also show that the existence of an x-monotone path and reporting it, if it exists, can be done with the same asymptotic time complexity. If the objective is to test the existence of an xy-monotone path between the given pair of points p and q avoiding the obstacles, and report it if exists, then our proposed algorithm needs O(n2s+nlogs+Mslogn) time with O(s) extra space, where Ms is the time complexity for computing the median of n elements in the read-only setup using O(s) extra space. Finally, we show that when the obstacles are unit squares instead of rectangles of arbitrary size, then there always exists a path of O(n) links between a pair of query points, and the path can be reported in O(nn) time using O(1) extra work-space. It is also shown that there is an instance where the minimum number of links in a path between a pair of specified points is O(n).The objective of the Path-Query(p,q) in the in-place setup is to preprocess the input rectangles in a data structure in the input array itself such that for any pair of query points p and q, a rectilinear path can be reported efficiently. Here we propose an algorithm with O(nlogn) preprocessing time and O(n3/4+) query time, where is the number of links (bends) in the path. Both the preprocessing and query answering need O(1) extra space. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.dam.2016.05.031 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Rectilinear path problem,In-place and read-only model of computation,Constant work-space | Combinatorics,Disjoint sets,Mathematics | Conference |
Volume | Issue | ISSN |
228 | C | 0166-218X |
Citations | PageRank | References |
1 | 0.38 | 14 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Binay K. Bhattacharya | 1 | 332 | 49.20 |
| Minati De | 2 | 45 | 10.11 |
| Anil Maheshwari | 3 | 869 | 104.47 |
| Subhas C. Nandy | 4 | 285 | 49.55 |
| Sasanka Roy | 5 | 31 | 13.37 |