Optimal shortest path queries in a simple polygon

DOI10.1016/0022-0000(89)90041-XzbMATH Open0681.68065OpenAlexW2038699153MaRDI QIDQ1823689FDOQ1823689

Authors: Leonidas Guibas, John 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

Recommendations

• scientific article; zbMATH DE number 742973
• Shortest Path Queries in Polygonal Domains
• AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
• \(L_{1}\) shortest path queries in simple polygons
• A new data structure for shortest path queries in a simple polygon
• Approximate shortest paths in simple polyhedra
• Optimal Shortest Path and Minimum-Link Path Queries between Two Convex Polygons inside a Simple Polygonal Obstacle
• Shortest path in a polygon using sublinear space
• Shortest Path in a Polygon using Sublinear Space.
• Query-point visibility constrained shortest paths in simple polygons

zbMATH Keywords

computational geometrysimple polygonsshortest path moving

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Maintenance of configurations in the plane
• Geometric applications of a matrix-searching algorithm
• Optimal Point Location in a Monotone Subdivision
• Euclidean shortest paths in the presence of rectilinear barriers
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon

Cited In (91)

• Algorithms for approximate shortest path queries on weighted polyhedral surfaces
• An algorithmic approach to some problems in terrain navigation
• Computing minimum length paths of a given homotopy class
• Parallel methods for visibility and shortest-path problems in simple polygons
• A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
• A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
• Memory-constrained algorithms for simple polygons
• Approximate Shortest Paths in Polygons with Violations
• Geodesic-preserving polygon simplification
• Digital Deformable Model Simulating Active Contours
• Computing simple paths from given points inside a polygon
• Polynomially solvable cases of the bipartite traveling salesman problem
• Voronoi diagrams for a moderate-sized point-set in a simple polygon
• Shortest paths in simple polygons with polygon-meet constraints
• Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon
• Computing the external geodesic diameter of a simple polygon
• On maximum flows in polyhedral domains
• Implicitly representing arrangements of lines or segments
• Finding a closet visible vertex pair between two polygons
• Largest triangle inside a terrain
• Triangulating a simple polygon in linear time
• An O\((n\log n)\) algorithm for the zoo-keeper's problem
• Fast computation of shortest watchman routes in simple polygons
• Convex hulls in polygonal domains
• Ray shooting in polygons using geodesic triangulations
• Visibility and intersection problems in plane geometry
• Generating random polygons with given vertices
• Shortest Path Queries in Polygonal Domains
• The geodesic 2-center problem in a simple polygon
• Title not available (Why is that?)
• Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions
• The discrete Voronoi game in a simple polygon
• Relative convex hulls in semi-dynamic arrangements
• Two linear-time algorithms for computing the minimum length polygon of a digital contour
• Shortest path planning for a tethered robot
• Dynamic data structures for \(k\)-nearest neighbor queries
• Computing external farthest neighbors for a simple polygon
• A new data structure for shortest path queries in a simple polygon
• Rectilinear paths among rectilinear obstacles
• SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS
• Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
• Space-time trade-offs for stack-based algorithms
• An O(n log n) ALGORITHM FOR FINDING A SHORTEST CENTRAL LINK SEGMENT
• A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon
• Special subgraphs of weighted visibility graphs
• Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour
• Asynchronous deterministic rendezvous in bounded terrains
• Improved dynamic geodesic nearest neighbor searching in a simple polygon
• The geodesic diameter of polygonal domains
• Querying two boundary points for shortest paths in a polygonal domain
• Computing an \(L_1\) shortest path among splinegonal obstacles in the plane
• Shortest Path in a Polygon using Sublinear Space.
• An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
• Querying two boundary points for shortest paths in a polygonal domain (extended abstract)
• Efficient piecewise-linear function approximation using the uniform metric
• \(L_{1}\) shortest path queries in simple polygons
• Finding a shortest Hamiltonian path inside a simple polygon
• Geometric path problems with violations
• Dynamic algorithms for visibility polygons in simple polygons
• \(L_1\) geodesic farthest neighbors in a simple polygon and related problems
• Visiting a Polygon on the Optimal Way to a Query Point
• Piercing pairwise intersecting geodesic disks by five points
• Algorithms for Computing Diffuse Reflection Paths in Polygons
• Reprint of: Memory-constrained algorithms for simple polygons
• The geodesic farthest-point Voronoi diagram in a simple polygon
• Piercing pairwise intersecting geodesic disks
• Title not available (Why is that?)
• Approximate Shortest Path Queries Using Voronoi Duals
• Shortest-Path Queries in Geometric Networks
• Shortest path to a segment and quickest visibility queries
• ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
• On Romeo and Juliet problems: minimizing distance-to-sight
• Partially walking a polygon
• On Romeo and Juliet problems: minimizing distance-to-sight
• Partially Walking a Polygon
• A divide-and-conquer algorithm for two-point L1 shortest path queries in polygonal domains
• Uniformly monotone partitioning of polygons
• k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON
• Large \(k\)-gons in a 1.5D terrain
• Away from each other
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• Efficient \(k\)-center algorithms for planar points in convex position
• Query-points visibility constraint minimum link paths in simple polygons
• The polygon burning problem
• On flipping the Fréchet distance
• k-pairs non-crossing shortest paths in a simple polygon
• A new balanced subdivision of a simple polygon for time-space trade-off algorithms
• Maximal distortion of geodesic diameters in polygonal domains
• FINDING AN OPTIMAL BRIDGE BETWEEN TWO POLYGONS
• IMPROVING SHORTEST PATHS IN THE DELAUNAY TRIANGULATION
• Shortest paths and convex hulls in 2D complexes with non-positive curvature

This page was built for publication: Optimal shortest path queries in a simple polygon

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