Euclidean shortest paths in the presence of rectilinear barriers

DOI10.1002/NET.3230140304zbMATH Open0545.90098OpenAlexW2032159439WikidataQ30047557 ScholiaQ30047557MaRDI QIDQ3337244FDOQ3337244

Authors:

Publication date: 1984

Published in: Networks (Search for Journal in Brave)

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

Recommendations

• scientific article; zbMATH DE number 3845073
• Rectilinear shortest paths in the presence of rectangular barriers
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
• Shortest paths in the plane with convex polygonal obstacles
• Finding shortest paths in the plane in the presence of barriers to travel (for any \(l_ p\)-norm)

zbMATH Keywords

visibility graphEuclidean shortest pathshortest-path treeplanar algorithmsrectilinear barriers

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35)

Cited In (97)

• The furthest-site geodesic Voronoi diagram
• Shortest path between two simple polygons
• SMOOTHING IMPRECISE 1.5D TERRAINS
• Minimum polygonal separation
• On bends and distances of paths among obstacles in two-layer interconnection model
• A survey of motion planning and related geometric algorithms
• Some computational aspects of geodesic convex sets in a simple polygon
• GUARDING ART GALLERIES BY GUARDING WITNESSES
• Visibility graphs and obstacle-avoiding shortest paths
• Optimal shortest path queries in a simple polygon
• An algorithmic approach to some problems in terrain navigation
• Parallel algorithms for shortest path problems in polygons
• Computing minimum length paths of a given homotopy class
• Parallel methods for visibility and shortest-path problems in simple polygons
• Shortest paths among transient obstacles
• On the geodesic Voronoi diagram of point sites in a simple polygon
• Approximate convex decomposition of polygons
• Characterizing and recognizing the visibility graph of a funnel-shaped polygon
• Visibility and ray shooting queries in polygonal domains
• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• Computing geodesic furthest neighbors in simple polygons
• OPTIMAL POLYGON COVER PROBLEMS AND APPLICATIONS
• Minimal link visibility paths inside a simple polygon
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Computing the external geodesic diameter of a simple polygon
• A new algorithm for shortest paths among obstacles in the plane
• A linear-time algorithm for the geodesic center of a simple polygon
• Finding shortest path in the presence of barriers: an alternate approach
• Maximising the worth of nascent networks
• Translating polygons with applications to hidden surface removal
• Finding a manhattan path and related problems
• Largest triangle inside a terrain
• Ray shooting in polygons using geodesic triangulations
• Computing the link center of a simple polygon
• Topologically sweeping an arrangement
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Vertex-colored encompassing graphs
• Fastest path across constrained moving rectilinear obstacles
• Shortest polygonal paths in space
• Relative convex hulls in semi-dynamic arrangements
• Existence and computation of tours through imprecise points
• Shortest path planning for a tethered robot
• Visibility between two edges of a simple polygon
• Computing external farthest neighbors for a simple polygon
• Euclidean shortest paths. Exact or approximate algorithms.
• Rectilinear paths among rectilinear obstacles
• Parallel rectilinear shortest paths with rectangular obstacles
• Finding shortest paths in the presence of orthogonal obstacles using a combined L 1 and link metric
• Computation of arc length in the presence of barriers in networks
• Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
• An optimal algorithm for computing a minimum nested nonconvex polygon
• Shortest curves in planar regions with curved boundary
• Finding shortest paths in the plane in the presence of barriers to travel (for any \(l_ p\)-norm)
• The application of \(\psi\)-transform for determining a near-optimal path in the presence of polyhedral obstacles
• Blaschke-type theorem and separation of disjoint closed geodesic convex sets
• Computing the geodesic center of a simple polygon
• Application of the A\(^*\) algorithm to problems of the Euclidean shortest paths in the plane with polygonal obstacles
• On separating two simple polygons by a single translation
• Efficient piecewise-linear function approximation using the uniform metric
• Computing homotopic shortest paths efficiently
• Rectilinear shortest paths in the presence of rectangular barriers
• Algorithms for Computing Diffuse Reflection Paths in Polygons
• Visibility of disjoint polygons
• Voronoi game on polygons
• Removing edge-node intersections in drawings of graphs
• Dynamic maintenance of shortest path trees in simple polygons
• ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
• Voronoi diagrams with barriers and on polyhedra for minimal path planning
• Tracing compressed curves in triangulated surfaces
• Title not available (Why is that?)
• Negative results on characterizing visibility graphs
• Title not available (Why is that?)
• k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON
• An optimal algorithm to compute the inverse beacon attraction region
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• Euclidean TSP in narrow strips
• Voronoi games using geodesics
• Drawing Shortest Paths in Geodetic Graphs
• Approximation algorithms for the two-watchman route in a simple polygon
• Shortest paths in the plane with obstacle violations
• Drawing Shortest Paths in Geodetic Graphs
• Voronoi diagrams in the moscow metric
• CUTTING OUT POLYGONS WITH A CIRCULAR SAW
• POINT VISIBILITY GRAPHS AND ${\mathcal O}$-CONVEX COVER
• Inserting Multiple Edges into a Planar Graph
• Title not available (Why is that?)
• Spatial Distribution of Traffic Flow in a Rectangular City with a Grid Network and a Rectangular Barrier
• k-pairs non-crossing shortest paths in a simple polygon
• Multiple shooting approach for finding approximately shortest paths for autonomous robots in unknown environments in 2D
• Finding shortest paths in a sequence of triangles in 3D by the planar unfolding
• Finding shortest paths in a sequence of triangles in 3D by the method of orienting curves
• Shortest paths in the plane with obstacle violations
• Finding globally shortest paths through a sequence of adjacent triangles by the method of orienting curves
• Optimal placement of base stations in border surveillance using limited capacity drones
• Maximal distortion of geodesic diameters in polygonal domains
• Efficient computation of the geodesic Voronoi diagram of points in a simple polygon
• Shortest paths and convex hulls in 2D complexes with non-positive curvature

This page was built for publication: Euclidean shortest paths in the presence of rectilinear barriers

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