An Optimal Algorithm for Euclidean Shortest Paths in the Plane

DOI10.1137/S0097539795289604zbMath0939.68157OpenAlexW2058510050MaRDI QIDQ4268866

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539795289604

zbMATH Keywords

shortest path obstacle avoidance Euclidean distance planar subdivision weighted distance shortest path map quad-tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Software, source code, etc. for problems pertaining to geometry (51-04) Data structures (68P05)

Related Items

Rectilinear link diameter and radius in a rectilinear polygonal domain, Computing the geodesic centers of a polygonal domain, SHORTEST DESCENDING PATHS: TOWARDS AN EXACT ALGORITHM, Planar rectilinear shortest path computation using corridors, Touring a sequence of disjoint polygons: complexity and extension, Flying over a polyhedral terrain, Characterizations of Restricted Pairs of Planar Graphs Allowing Simultaneous Embedding with Fixed Edges, An optimal-time algorithm for shortest paths on realistic polyhedra, Shortest Path Problems on a Polyhedral Surface, Routing among convex polygonal obstacles in the plane, Navigating Weighted Regions with Scattered Skinny Tetrahedra, Shortest paths among transient obstacles, Shortest paths in simple polygons with polygon-meet constraints, ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE, The geodesic diameter of polygonal domains, Routing in polygonal domains, Algorithms for approximate shortest path queries on weighted polyhedral surfaces, Shortest paths in the plane with obstacle violations, Computing \(L_1\) shortest paths among polygonal obstacles in the plane, On geometric path query problems, A Near-Optimal Algorithm for Shortest Paths Among Curved Obstacles in the Plane, A note on visibility-constrained Voronoi diagrams, Kinetic Geodesic Voronoi Diagrams in a Simple Polygon, Shortest Journeys in Directed Temporal Graphs, A novel approach for modeling order picking paths, Visiting a Polygon on the Optimal Way to a Query Point, Querying two boundary points for shortest paths in a polygonal domain, Shortest Path Queries in Polygonal Domains, An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons, Farthest-point Voronoi diagrams in the presence of rectangular obstacles, Maximal distortion of geodesic diameters in polygonal domains, Shortest path planning for a tethered robot, Pursuit-evasion games in the presence of obstacles, Reachable region query and its applications, Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges, Link distance and shortest path problems in the plane, Shortest paths and convex hulls in 2D complexes with non-positive curvature, Asynchronous deterministic rendezvous in bounded terrains, Geodesics in CAT(0) cubical complexes, Shortest path problems on a polyhedral surface, Approximate Shortest Paths in Polygons with Violations, Shortest rectilinear path queries to rectangles in a rectangular domain, Shortest-Path Queries in Geometric Networks, APPROXIMATE SHORTEST HOMOTOPIC PATHS IN WEIGHTED REGIONS, Curvature-constrained traveling salesman tours for aerial surveillance in scenarios with obstacles, Maximum thick paths in static and dynamic environments, Finding the shortest path by evolving junctions on obstacle boundaries (E-JOB): an initial value ODE's approach, An optimal-time algorithm for shortest paths on a convex polytope in three dimensions, Lower bounds for computing geometric spanners and approximate shortest paths, Approximation algorithms for shortest descending paths in terrains, Curves that must be retraced, A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation, \(L_{1}\) cheapest paths in ``Fjord scenery, Unnamed Item, ON GEOMETRIC PATH QUERY PROBLEMS, Honey-pot constrained searching with local sensory information, An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges, Finding a Rectilinear Shortest Path in R 2 Using Corridor Based Staircase Structures, EXACT AND APPROXIMATION ALGORITHMS FOR FINDING AN OPTIMAL BRIDGE CONNECTING TWO SIMPLE POLYGONS, Unnamed Item, Rectilinear link diameter and radius in a rectilinear polygonal domain, Unnamed Item, Unnamed Item, Efficient Boustrophedon multi-robot coverage: An algorithmic approach, Link Distance and Shortest Path Problems in the Plane, Minimizing Distance-to-Sight in Polygonal Domains, Quickest visibility queries in polygonal domains, The shortest path AMID 3-D polyhedral obstacles, Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time, The transportation metric and related problems, Computing an \(L_1\) shortest path among splinegonal obstacles in the plane, Computing Shortest Paths in the Plane with Removable Obstacles, How to Keep an Eye on Small Things, Minimum Cell Connection in Line Segment Arrangements, GEODESIC-PRESERVING POLYGON SIMPLIFICATION, Routing in Polygonal Domains, A wavefront approach to center location problems with barriers