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
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, 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
