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

DOI10.1016/0020-0190(91)90064-OzbMATH Open0738.68021OpenAlexW2004884735MaRDI QIDQ1178232FDOQ1178232

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

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

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)

Cites Work

• Maintenance of configurations in the plane
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Optimal shortest path queries in a simple polygon
• An optimal visibility graph algorithm for triangulated simple polygons
• Title not available (Why is that?)

Cited In (25)

• Piercing pairwise intersecting geodesic disks
• Title not available (Why is that?)
• On Romeo and Juliet problems: minimizing distance-to-sight
• On Romeo and Juliet problems: minimizing distance-to-sight
• Optimal shortest path queries in a simple polygon
• 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
• ON GEOMETRIC PATH QUERY PROBLEMS
• Computing simple paths from given points inside a polygon
• 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
• Title not available (Why is that?)
• 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)