Euclidean shortest paths in the presence of rectilinear barriers
From MaRDI portal
Publication:3337244
DOI10.1002/net.3230140304zbMath0545.90098OpenAlexW2032159439WikidataQ30047557 ScholiaQ30047557MaRDI QIDQ3337244
No author found.
Publication date: 1984
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230140304
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35)
Related Items
Computing minimum length paths of a given homotopy class ⋮ Ray shooting in polygons using geodesic triangulations ⋮ Spatial Distribution of Traffic Flow in a Rectangular City with a Grid Network and a Rectangular Barrier ⋮ Minimal link visibility paths inside a simple polygon ⋮ Visibility of disjoint polygons ⋮ Drawing Shortest Paths in Geodetic Graphs ⋮ Maximising the worth of nascent networks ⋮ Translating polygons with applications to hidden surface removal ⋮ Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric ⋮ Visibility between two edges of a simple polygon ⋮ Characterizing and recognizing the visibility graph of a funnel-shaped polygon ⋮ CUTTING OUT POLYGONS WITH A CIRCULAR SAW ⋮ Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons ⋮ Minimum polygonal separation ⋮ A new algorithm for shortest paths among obstacles in the plane ⋮ Negative results on characterizing visibility graphs ⋮ Computing the link center of a simple polygon ⋮ Parallel algorithms for shortest path problems in polygons ⋮ OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS ⋮ Shortest path between two simple polygons ⋮ Efficient piecewise-linear function approximation using the uniform metric ⋮ Rectilinear shortest paths in the presence of rectangular barriers ⋮ On the geodesic Voronoi diagram of point sites in a simple polygon ⋮ An algorithmic approach to some problems in terrain navigation ⋮ ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE ⋮ Topologically sweeping an arrangement ⋮ A survey of motion planning and related geometric algorithms ⋮ Shortest paths in the plane with obstacle violations ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Voronoi games using geodesics ⋮ Efficient computation of the geodesic Voronoi diagram of points in a simple polygon ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ Maximal distortion of geodesic diameters in polygonal domains ⋮ Shortest path planning for a tethered robot ⋮ Voronoi diagrams in the moscow metric ⋮ Computing homotopic shortest paths efficiently ⋮ Finding globally shortest paths through a sequence of adjacent triangles by the method of orienting curves ⋮ Shortest paths and convex hulls in 2D complexes with non-positive curvature ⋮ An optimal algorithm for computing a minimum nested nonconvex polygon ⋮ Unnamed Item ⋮ Largest triangle inside a terrain ⋮ Visibility graphs and obstacle-avoiding shortest paths ⋮ Computing external farthest neighbors for a simple polygon ⋮ Relative convex hulls in semi-dynamic arrangements ⋮ Finding Shortest Paths in a Sequence of Triangles in 3D by the Planar Unfolding ⋮ Blaschke-type theorem and separation of disjoint closed geodesic convex sets ⋮ Finding shortest paths in a sequence of triangles in 3D by the method of orienting curves ⋮ \(L_ 1\) shortest paths among polygonal obstacles in the plane ⋮ EXISTENCE AND COMPUTATION OF TOURS THROUGH IMPRECISE POINTS ⋮ Parallel rectilinear shortest paths with rectangular obstacles ⋮ The application of \(\psi\)-transform for determining a near-optimal path in the presence of polyhedral obstacles ⋮ Parallel methods for visibility and shortest-path problems in simple polygons ⋮ Some Computational Aspects of Geodesic Convex Sets in a Simple Polygon ⋮ The furthest-site geodesic Voronoi diagram ⋮ Shortest curves in planar regions with curved boundary ⋮ Visibility and ray shooting queries in polygonal domains ⋮ SMOOTHING IMPRECISE 1.5D TERRAINS ⋮ k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON ⋮ POINT VISIBILITY GRAPHS AND ${\mathcal O}$-CONVEX COVER ⋮ Computing the geodesic center of a simple polygon ⋮ Computing the external geodesic diameter of a simple polygon ⋮ Algorithms for Computing Diffuse Reflection Paths in Polygons ⋮ Approximate convex decomposition of polygons ⋮ A linear-time algorithm for the geodesic center of a simple polygon ⋮ Unnamed Item ⋮ Voronoi game on polygons ⋮ Vertex-colored encompassing graphs ⋮ GUARDING ART GALLERIES BY GUARDING WITNESSES ⋮ Tracing compressed curves in triangulated surfaces ⋮ Fastest path across constrained moving rectilinear obstacles ⋮ Shortest polygonal paths in space ⋮ Voronoi diagrams with barriers and on polyhedra for minimal path planning ⋮ Computing geodesic furthest neighbors in simple polygons ⋮ Optimal shortest path queries in a simple polygon ⋮ On separating two simple polygons by a single translation ⋮ Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time ⋮ Optimal placement of base stations in border surveillance using limited capacity drones ⋮ Rectilinear paths among rectilinear obstacles ⋮ An optimal algorithm to compute the inverse beacon attraction region ⋮ Drawing Shortest Paths in Geodetic Graphs ⋮ Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time ⋮ Weak visibility queries of line segments in simple polygons ⋮ Removing edge-node intersections in drawings of graphs
