Rectilinear Path Problems among Rectilinear Obstacles Revisited

DOI10.1137/S0097539792229672MaRDI QIDQ4842114zbMATH OpenOpenAlexFDO

Authors

Publication date 26 July 1995

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539792229672

zbMATH Keywords

minimum-bend pathpath preserving graphrectilinear collision-free paths

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• ON BENDS AND LENGTHS OF RECTILINEAR PATHS: A GRAPH-THEORETIC APPROACH
• A nearly optimal algorithm for finding \(L _{1}\) shortest paths among polygonal obstacles in the plane
• scientific article; zbMATH DE number 177558
• Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
• Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures

Cited in

(26)

• Finding a region with the minimum total L₁ distance from prescribed terminals
• Minimum-link shortest paths for polygons amidst rectilinear obstacles
• Shortest paths among transient obstacles
• Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
• Rectilinear shortest paths among transient obstacles
• Rectilinear path problems in restricted memory setup
• Computation of arc length in the presence of barriers in networks
• Rectilinear paths with minimum segment lengths
• Minimum-link paths revisited
• Rectilinear paths among rectilinear obstacles
• Rectilinear shortest path and rectilinear minimum spanning tree with neighborhoods
• ON BENDS AND LENGTHS OF RECTILINEAR PATHS: A GRAPH-THEORETIC APPROACH
• Paths through a maze of rectangles
• scientific article; zbMATH DE number 177558 (Why is no real title available?)
• Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
• ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS
• On geometric path query problems
• Computing shortest paths in the plane with removable obstacles
• Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures
• An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model
• Applications of a numbering scheme for polygonal obstacles in the plane
• Proximity problems for points on a rectilinear plane with rectangular obstacles
• Computing skeletons for rectilinearly convex obstacles in the rectilinear plane
• Planar rectilinear shortest path computation using corridors
• Finding shortest path in the presence of barriers: an alternate approach
• Finding rectilinear least cost paths in the presence of convex polygonal congested regions

This page was built for publication: Rectilinear Path Problems among Rectilinear Obstacles Revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4842114)