A new data structure for shortest path queries in a simple polygon

DOI10.1016/0020-0190(91)90064-OMaRDI QIDQ1178232zbMATH OpenOpenAlexFDO

Authors John Hershberger

Publication date 26 June 1992

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90064-o

zbMATH Keywords

convex hull

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Optimal shortest path queries in a simple polygon
• scientific article; zbMATH DE number 512835
• AN OPTIMAL DATA STRUCTURE FOR SHORTEST RECTILINEAR PATH QUERIES IN A SIMPLE RECTILINEAR POLYGON
• \(L_{1}\) shortest path queries in simple polygons

Cites work

• scientific article; zbMATH DE number 432762 (Why is no real title available?)
• An optimal visibility graph algorithm for triangulated simple polygons
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Maintenance of configurations in the plane
• Optimal shortest path queries in a simple polygon

Cited in

(25)

• Piercing pairwise intersecting geodesic disks
• scientific article; zbMATH DE number 7559259 (Why is no real title available?)
• On Romeo and Juliet problems: minimizing distance-to-sight
• Optimal shortest path queries in a simple polygon
• On Romeo and Juliet problems: minimizing distance-to-sight
• 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
• Computing simple paths from given points inside a polygon
• ON GEOMETRIC PATH QUERY PROBLEMS
• 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
• Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon
• Shortest zookeeper's routes in simple polygons
• An O\((n\log n)\) algorithm for the zoo-keeper's problem
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• Ray shooting in polygons using geodesic triangulations
• Minimum weight pseudo-triangulations
• scientific article; zbMATH DE number 742973 (Why is no real title available?)
• Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time
• A Time-Space Trade-off for the Shortest Path Tree in a Simple Polygon
• Improved dynamic geodesic nearest neighbor searching in a simple polygon
• Computing an \(L_1\) shortest path among splinegonal obstacles in the plane
• An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
• Efficient piecewise-linear function approximation using the uniform metric
• Piercing pairwise intersecting geodesic disks by five points

This page was built for publication: A new data structure for 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 Q1178232)