Optimal shortest path queries in a simple polygon

DOI10.1016/0022-0000(89)90041-XMaRDI QIDQ1823689zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational geometrysimple polygonsshortest path moving

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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

Cites work

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

Cited in

(only showing first 100 items - show all)

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

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)