Finding minimum rectilinear distance paths in the presence of barriers

DOI10.1002/net.3230110307zbMath0459.90082OpenAlexW2062367161MaRDI QIDQ3910336

Richard C. Larson, Victor O. K. Li

Publication date: 1981

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230110307

zbMATH Keywords

computational complexityefficient algorithmpolygonal barrierspresence of barriersDijkstra-type iterationminimum rectilinear distance paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (29)

Computing minimum length paths of a given homotopy class ⋮ Spatial Distribution of Traffic Flow in a Rectangular City with a Grid Network and a Rectangular Barrier ⋮ Computation of arc length in the presence of barriers in networks ⋮ Mixed planar/network facility location problems ⋮ Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric ⋮ Rectilinear short path queries among rectangular obstacles ⋮ Optimal piecewise linear motion of an object among obstacles ⋮ On the accuracy of demand point solutions to the planar, Manhattan metric, p-median problem, with and without barriers to travel ⋮ Dominance rules for the optimal placement of a finite-size facility in an existing layout ⋮ Rectilinear shortest paths in the presence of rectangular barriers ⋮ Placing a finite size facility with a center objective on a rectangular plane with barriers ⋮ Median location problem with two probabilistic line barriers: extending the Hooke and Jeeves algorithm ⋮ Finding shortest path in the presence of barriers: an alternate approach ⋮ Computing \(L_1\) shortest paths among polygonal obstacles in the plane ⋮ \(L_ 1\) shortest paths among polygonal obstacles in the plane ⋮ On finding a shortest isothetic path and its monotonicity inside a digital object ⋮ Proximity problems for points on a rectilinear plane with rectangular obstacles ⋮ Parallel rectilinear shortest paths with rectangular obstacles ⋮ Finding rectilinear least cost paths in the presence of convex polygonal congested regions ⋮ Rectilinear distance to a facility in the presence of a square barrier ⋮ A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric ⋮ ON CONNECTING RED AND BLUE RECTILINEAR POLYGONAL OBSTACLES WITH NONINTERSECTING MONOTONE RECTILINEAR PATHS ⋮ Supply facility and input/output point locations in the presence of barriers ⋮ Facility placement with sub-aisle design in an existing layout ⋮ An efficient algorithm for facility location in the presence of forbidden regions ⋮ Rectilinear paths among rectilinear obstacles ⋮ Finding shortest paths in the plane in the presence of barriers to travel (for any \(l_ p\)-norm) ⋮ On rectilinear link distance ⋮ Removing edge-node intersections in drawings of graphs

This page was built for publication: Finding minimum rectilinear distance paths in the presence of barriers