Rectilinear short path queries among rectangular obstacles

DOI10.1016/0020-0190(96)00020-8MaRDI QIDQ1351630zbMATH OpenOpenAlexWikidataFDO

Authors Danny Z. Chen, Kevin S. Klenk

Publication date 27 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(96)00020-8

zbMATH Keywords

AlgorithmsAnalysis of algorithmsComputational geometryData structuresDesign of algorithmsShortest path

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Efficient approximate shortest-path queries among isothetic rectangular obstacles
• Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
• Parallel rectilinear shortest paths with rectangular obstacles
• scientific article; zbMATH DE number 512835

Cites work

• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane
• Applications of a Planar Separator Theorem
• Efficient approximate shortest-path queries among isothetic rectangular obstacles
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding level-ancestors in trees
• Finding minimum rectilinear distance paths in the presence of barriers
• scientific article; zbMATH DE number 3648730 (Why is no real title available?)
• scientific article; zbMATH DE number 30300 (Why is no real title available?)
• scientific article; zbMATH DE number 910885 (Why is no real title available?)
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• On parallel rectilinear obstacle-avoiding paths
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions
• ORTHOGONAL SHORTEST ROUTE QUERIES AMONG AXES PARALLEL RECTANGULAR OBSTACLES
• Parallel rectilinear shortest paths with rectangular obstacles
• Rectilinear shortest paths in the presence of rectangular barriers
• SHORTEST RECTILINEAR PATHS AMONG WEIGHTED OBSTACLE

Cited in

(24)

• Parallel rectilinear shortest paths with rectangular obstacles
• On parallel rectilinear obstacle-avoiding paths
• Computing an \(L_1\) shortest path among splinegonal obstacles in the plane
• Rectilinear path problems in restricted memory setup
• SHORTEST RECTILINEAR PATHS AMONG WEIGHTED OBSTACLE
• SHORTEST PATH QUERIES IN RECTILINEAR WORLDS
• Efficient Computation of Rectilinear Geodesic Voronoi Neighbor in the Presence of Obstacles
• scientific article; zbMATH DE number 512835 (Why is no real title available?)
• ORTHOGONAL SHORTEST ROUTE QUERIES AMONG AXES PARALLEL RECTANGULAR OBSTACLES
• Planar spanners and approximate shortest path queries among obstacles in the plane
• ON GEOMETRIC PATH QUERY PROBLEMS
• ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS
• scientific article; zbMATH DE number 910885 (Why is no real title available?)
• AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
• Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
• Efficient approximate shortest-path queries among isothetic rectangular obstacles
• Rectilinear path problems in restricted memory setup
• The Length of Shortest Vertex Paths in Binary Occupancy Grids Compared to Shortest r-Constrained Ones
• Shortest rectilinear path queries to rectangles in a rectangular domain
• Shortest rectilinear path queries to rectangles in a rectangular domain
• Applications of a numbering scheme for polygonal obstacles in the plane
• Efficient computation of rectilinear geodesic Voronoi neighbor in presence of obstacles
• Proximity problems for points on a rectilinear plane with rectangular obstacles
• Planar rectilinear shortest path computation using corridors

This page was built for publication: Rectilinear short path queries among rectangular obstacles

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