Optimal shortest path queries in a simple polygon
From MaRDI portal
Publication:1823689
DOI10.1016/0022-0000(89)90041-XzbMath0681.68065OpenAlexW2038699153MaRDI QIDQ1823689
Leonidas J. Guibas, J. E. Hershberger
Publication date: 1989
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(89)90041-x
Related Items (78)
The geodesic 2-center problem in a simple polygon ⋮ Computing minimum length paths of a given homotopy class ⋮ Ray shooting in polygons using geodesic triangulations ⋮ Computing simple paths from given points inside a polygon ⋮ Finding a closet visible vertex pair between two polygons ⋮ The polygon burning problem ⋮ FINDING AN OPTIMAL BRIDGE BETWEEN TWO POLYGONS ⋮ Efficient piecewise-linear function approximation using the uniform metric ⋮ Memory-constrained algorithms for simple polygons ⋮ Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon ⋮ An algorithmic approach to some problems in terrain navigation ⋮ ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE ⋮ The geodesic diameter of polygonal domains ⋮ Algorithms for approximate shortest path queries on weighted polyhedral surfaces ⋮ Generating random polygons with given vertices ⋮ Reprint of: Memory-constrained algorithms for simple polygons ⋮ A new balanced subdivision of a simple polygon for time-space trade-off algorithms ⋮ Away from each other ⋮ Dynamic data structures for \(k\)-nearest neighbor queries ⋮ Querying two boundary points for shortest paths in a polygonal domain ⋮ Shortest Path Queries in Polygonal Domains ⋮ Large \(k\)-gons in a 1.5D terrain ⋮ An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ Efficient \(k\)-center algorithms for planar points in convex position ⋮ Maximal distortion of geodesic diameters in polygonal domains ⋮ Shortest path planning for a tethered robot ⋮ Visibility and intersection problems in plane geometry ⋮ Shortest paths and convex hulls in 2D complexes with non-positive curvature ⋮ Geometric path problems with violations ⋮ On maximum flows in polyhedral domains ⋮ Asynchronous deterministic rendezvous in bounded terrains ⋮ Largest triangle inside a terrain ⋮ SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS ⋮ Computing external farthest neighbors for a simple polygon ⋮ Relative convex hulls in semi-dynamic arrangements ⋮ Triangulating a simple polygon in linear time ⋮ A new data structure for shortest path queries in a simple polygon ⋮ Piercing pairwise intersecting geodesic disks ⋮ Dynamic Algorithms for Visibility Polygons in Simple Polygons ⋮ Space-time trade-offs for stack-based algorithms ⋮ Shortest-Path Queries in Geometric Networks ⋮ Polynomially solvable cases of the bipartite traveling salesman problem ⋮ Special subgraphs of weighted visibility graphs ⋮ Parallel methods for visibility and shortest-path problems in simple polygons ⋮ \(L_{1}\) shortest path queries in simple polygons ⋮ Unnamed Item ⋮ k-pairs non-crossing shortest paths in a simple polygon ⋮ An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT ⋮ k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON ⋮ Computing the external geodesic diameter of a simple polygon ⋮ Algorithms for Computing Diffuse Reflection Paths in Polygons ⋮ Diffuse reflection radius in a simple polygon ⋮ Voronoi diagrams for a moderate-sized point-set in a simple polygon ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon ⋮ Implicitly representing arrangements of lines or segments ⋮ Partially Walking a Polygon ⋮ The geodesic farthest-point Voronoi diagram in a simple polygon ⋮ Two linear-time algorithms for computing the minimum length polygon of a digital contour ⋮ Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour ⋮ Digital Deformable Model Simulating Active Contours ⋮ Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time ⋮ The discrete Voronoi game in a simple polygon ⋮ Rectilinear paths among rectilinear obstacles ⋮ Computing an \(L_1\) shortest path among splinegonal obstacles in the plane ⋮ Computing a geodesic two-center of points in a simple polygon ⋮ Partially walking a polygon ⋮ On Romeo and Juliet problems: minimizing distance-to-sight ⋮ On Romeo and Juliet Problems: Minimizing Distance-to-Sight. ⋮ \(L_1\) geodesic farthest neighbors in a simple polygon and related problems ⋮ Piercing pairwise intersecting geodesic disks by five points ⋮ GEODESIC-PRESERVING POLYGON SIMPLIFICATION ⋮ Weak visibility queries of line segments in simple polygons ⋮ Query-Points Visibility Constraint Minimum Link Paths in Simple Polygons ⋮ An O\((n\log n)\) algorithm for the zoo-keeper's problem
Cites Work
This page was built for publication: Optimal shortest path queries in a simple polygon
