K-link rectilinear shortest paths among rectilinear obstacles in the plane

Valentin Polishchuk; Joseph S.B. Mitchell

K-link rectilinear shortest paths among rectilinear obstacles in the plane

Valentin Polishchuk
, Joseph S.B. Mitchell

Applied Mathematics and Statistics

Stony Brook University

Research output: Contribution to conference › Paper › peer-review

6 Scopus citations

Abstract

We present an algorithm for computing k-link rectilin- ear shortest paths among rectilinear obstacles in the plane. We extend the \continuous Dijkstra" paradigm to store the link distance information associated with each propagating \wavefront". Our algorithm runs in time O(kn log2 n) and space O(kn), where n is the num- ber of vertices of the obstacles. Previous algorithms for the problem had worst-case time complexity O(kn2). Our algorithm builds a j-link shortest path map, rooted at a given source s, for each j ≤ k. A short- est path query from s to a query point t can then be answered in time O(log n + j).

Original language	English
Pages	101-104
Number of pages	4
State	Published - 2005
Event	17th Canadian Conference on Computational Geometry, CCCG 2005 - Windsor, Canada Duration: Aug 10 2005 → Aug 12 2005

Conference

Conference	17th Canadian Conference on Computational Geometry, CCCG 2005
Country/Territory	Canada
City	Windsor
Period	08/10/05 → 08/12/05

Cite this

@conference{ef0a7bf6d6a442a88522b4fc45044da1,

title = "K-link rectilinear shortest paths among rectilinear obstacles in the plane",

abstract = "We present an algorithm for computing k-link rectilin- ear shortest paths among rectilinear obstacles in the plane. We extend the \textbackslash{}continuous Dijkstra{"} paradigm to store the link distance information associated with each propagating \textbackslash{}wavefront{"}. Our algorithm runs in time O(kn log2 n) and space O(kn), where n is the num- ber of vertices of the obstacles. Previous algorithms for the problem had worst-case time complexity O(kn2). Our algorithm builds a j-link shortest path map, rooted at a given source s, for each j ≤ k. A short- est path query from s to a query point t can then be answered in time O(log n + j).",

author = "Valentin Polishchuk and Mitchell, \{Joseph S.B.\}",

note = "Publisher Copyright: {\textcopyright} 2005 Canadian Conference on Computational Geometry. All rights reserved.; 17th Canadian Conference on Computational Geometry, CCCG 2005 ; Conference date: 10-08-2005 Through 12-08-2005",

year = "2005",

language = "English",

pages = "101--104",

}

TY - CONF

T1 - K-link rectilinear shortest paths among rectilinear obstacles in the plane

AU - Polishchuk, Valentin

AU - Mitchell, Joseph S.B.

PY - 2005

Y1 - 2005

N2 - We present an algorithm for computing k-link rectilin- ear shortest paths among rectilinear obstacles in the plane. We extend the \continuous Dijkstra" paradigm to store the link distance information associated with each propagating \wavefront". Our algorithm runs in time O(kn log2 n) and space O(kn), where n is the num- ber of vertices of the obstacles. Previous algorithms for the problem had worst-case time complexity O(kn2). Our algorithm builds a j-link shortest path map, rooted at a given source s, for each j ≤ k. A short- est path query from s to a query point t can then be answered in time O(log n + j).

AB - We present an algorithm for computing k-link rectilin- ear shortest paths among rectilinear obstacles in the plane. We extend the \continuous Dijkstra" paradigm to store the link distance information associated with each propagating \wavefront". Our algorithm runs in time O(kn log2 n) and space O(kn), where n is the num- ber of vertices of the obstacles. Previous algorithms for the problem had worst-case time complexity O(kn2). Our algorithm builds a j-link shortest path map, rooted at a given source s, for each j ≤ k. A short- est path query from s to a query point t can then be answered in time O(log n + j).

UR - https://www.scopus.com/pages/publications/85029923759

M3 - Paper

AN - SCOPUS:85029923759

SP - 101

EP - 104

T2 - 17th Canadian Conference on Computational Geometry, CCCG 2005

Y2 - 10 August 2005 through 12 August 2005

ER -

K-link rectilinear shortest paths among rectilinear obstacles in the plane

Abstract

Conference

Other files and links

Fingerprint

Cite this