New results on shortest paths in three dimensions

Joseph S.B. Mitchell; Micha Sharir

doi:10.1145/997817.997839

New results on shortest paths in three dimensions

Joseph S.B. Mitchell
, Micha Sharir

Applied Mathematics and Statistics

Stony Brook University

Tel Aviv University

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

51 Scopus citations

Abstract

We revisit the problem of computing shortest obstacle-avoiding paths among obstacles in three dimensions. We prove new hardness results, showing, e.g., that computing Euclidean shortest paths among sets of "stacked" axis-aligned rectangles is NP-complete, and that computing L ₁-shortest paths among disjoint balls is NP-complete. On the positive side, we present an efficient algorithm for computing an L ₁shortest path between two given points that lies on or above a given polyhedral terrain. We also give polynomial-time algorithms for some versions of stacked polygonal obstacles that are "terrain-like" and analyze the complexity of shortest path maps in the presence of parallel halfplane "walls".

Original language	English
Pages	124-133
Number of pages	10
DOIs	https://doi.org/10.1145/997817.997839
State	Published - 2004
Event	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: Jun 9 2004 → Jun 11 2004

Conference

Conference	Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Country/Territory	United States
City	Brooklyn, NY
Period	06/9/04 → 06/11/04

Keywords

Motion planning
NP-hardness
Shortest path
Terrain

Access to Document

10.1145/997817.997839

Cite this

@conference{182d3be06dcf4dfab0fb64001edcadb9,

title = "New results on shortest paths in three dimensions",

abstract = "We revisit the problem of computing shortest obstacle-avoiding paths among obstacles in three dimensions. We prove new hardness results, showing, e.g., that computing Euclidean shortest paths among sets of {"}stacked{"} axis-aligned rectangles is NP-complete, and that computing L 1-shortest paths among disjoint balls is NP-complete. On the positive side, we present an efficient algorithm for computing an L 1shortest path between two given points that lies on or above a given polyhedral terrain. We also give polynomial-time algorithms for some versions of stacked polygonal obstacles that are {"}terrain-like{"} and analyze the complexity of shortest path maps in the presence of parallel halfplane {"}walls{"}.",

keywords = "Motion planning, NP-hardness, Shortest path, Terrain",

author = "Mitchell, \{Joseph S.B.\} and Micha Sharir",

year = "2004",

doi = "10.1145/997817.997839",

language = "English",

pages = "124--133",

note = "Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) ; Conference date: 09-06-2004 Through 11-06-2004",

}

TY - CONF

T1 - New results on shortest paths in three dimensions

AU - Mitchell, Joseph S.B.

AU - Sharir, Micha

PY - 2004

Y1 - 2004

N2 - We revisit the problem of computing shortest obstacle-avoiding paths among obstacles in three dimensions. We prove new hardness results, showing, e.g., that computing Euclidean shortest paths among sets of "stacked" axis-aligned rectangles is NP-complete, and that computing L 1-shortest paths among disjoint balls is NP-complete. On the positive side, we present an efficient algorithm for computing an L 1shortest path between two given points that lies on or above a given polyhedral terrain. We also give polynomial-time algorithms for some versions of stacked polygonal obstacles that are "terrain-like" and analyze the complexity of shortest path maps in the presence of parallel halfplane "walls".

AB - We revisit the problem of computing shortest obstacle-avoiding paths among obstacles in three dimensions. We prove new hardness results, showing, e.g., that computing Euclidean shortest paths among sets of "stacked" axis-aligned rectangles is NP-complete, and that computing L 1-shortest paths among disjoint balls is NP-complete. On the positive side, we present an efficient algorithm for computing an L 1shortest path between two given points that lies on or above a given polyhedral terrain. We also give polynomial-time algorithms for some versions of stacked polygonal obstacles that are "terrain-like" and analyze the complexity of shortest path maps in the presence of parallel halfplane "walls".

KW - Motion planning

KW - NP-hardness

KW - Shortest path

KW - Terrain

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

U2 - 10.1145/997817.997839

DO - 10.1145/997817.997839

M3 - Paper

SP - 124

EP - 133

T2 - Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)

Y2 - 9 June 2004 through 11 June 2004

ER -

New results on shortest paths in three dimensions

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this