\(L_ 1\) shortest paths among polygonal obstacles in the plane
From MaRDI portal
Publication:1188116
DOI10.1007/BF01758836zbMath0753.68093OpenAlexW2063372577MaRDI QIDQ1188116
Publication date: 13 August 1992
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01758836
Related Items (49)
Optimal time-convex hull for a straight-line highway in \(L_p\)-metrics ⋮ Minimum-link shortest paths for polygons amidst rectilinear obstacles ⋮ A connectivity graph generation approach for Manhattan path calculation in detailed facility layout ⋮ Spatial Distribution of Traffic Flow in a Rectangular City with a Grid Network and a Rectangular Barrier ⋮ Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Saturation of Multidimensional 0-1 Matrices ⋮ Almost all permutation matrices have bounded saturation functions ⋮ Computation of arc length in the presence of barriers in networks ⋮ Planar rectilinear shortest path computation using corridors ⋮ Flying over a polyhedral terrain ⋮ Rectilinear short path queries among rectangular obstacles ⋮ Efficient approximate shortest-path queries among isothetic rectangular obstacles ⋮ Shortest paths among transient obstacles ⋮ Placing a finite size facility with a center objective on a rectangular plane with barriers ⋮ Finding shortest path in the presence of barriers: an alternate approach ⋮ Fastest-path planning for direction-dependent speed functions ⋮ Computing \(L_1\) shortest paths among polygonal obstacles in the plane ⋮ Aggregate-MAX Top-k Nearest Neighbor Searching in the L1 Plane ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ Range queries on uncertain data ⋮ Farthest-point Voronoi diagrams in the presence of rectangular obstacles ⋮ Rectilinear paths with minimum segment lengths ⋮ Shortest rectilinear path queries to rectangles in a rectangular domain ⋮ Group nearest-neighbor queries in the \(L_1\) plane ⋮ Proximity problems for points on a rectilinear plane with rectangular obstacles ⋮ Conditional facility location problems with continuous demand and a polygonal barrier ⋮ The 1-\textsc{Center} and 1-\textsc{Highway} problem revisited ⋮ Finding rectilinear least cost paths in the presence of convex polygonal congested regions ⋮ Computing the \(L_1\) geodesic diameter and center of a polygonal domain ⋮ Finding the shortest path by evolving junctions on obstacle boundaries (E-JOB): an initial value ODE's approach ⋮ Rectilinear distance to a facility in the presence of a square barrier ⋮ Lower bounds for computing geometric spanners and approximate shortest paths ⋮ \(L_{1}\) cheapest paths in ``Fjord scenery ⋮ An efficient direct approach for computing shortest rectilinear paths among obstacles in a two-layer interconnection model ⋮ Unnamed Item ⋮ ON GEOMETRIC PATH QUERY PROBLEMS ⋮ All Farthest Neighbors in the Presence of Highways and Obstacles ⋮ Saturation Problems about Forbidden 0-1 Submatrices ⋮ Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures ⋮ Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ An efficient algorithm for facility location in the presence of forbidden regions ⋮ OPTIMAL CONSTRUCTION OF THE CITY VORONOI DIAGRAM ⋮ Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane ⋮ Rectilinear paths among rectilinear obstacles ⋮ Computing an \(L_1\) shortest path among splinegonal obstacles in the plane ⋮ GEODESIC-PRESERVING POLYGON SIMPLIFICATION ⋮ The \(k\)-nearest-neighbor Voronoi diagram revisited ⋮ Angle-restricted Steiner arborescences for flow map layout ⋮ A wavefront approach to center location problems with barriers
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- An algorithm for shortest-path motion in three dimensions
- Visibility of disjoint polygons
- A sweepline algorithm for Voronoi diagrams
- Davenport-Schinzel theory of matrices
- A new algorithm for shortest paths among obstacles in the plane
- On Some Distance Problems in Fixed Orientations
- The Discrete Geodesic Problem
- Euclidean shortest paths in the presence of rectilinear barriers
- Some methods of computational geometry applied to computer graphics
- Optimal Point Location in a Monotone Subdivision
- On Shortest Paths in Polyhedral Spaces
- Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
- Finding minimum rectilinear distance paths in the presence of barriers
- A New Approach to Planar Point Location
- Optimal Search in Planar Subdivisions
- An Extremal Problem on Sparse 0-1 Matrices
- On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
- The weighted region problem
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
This page was built for publication: \(L_ 1\) shortest paths among polygonal obstacles in the plane
