A new data structure for shortest path queries in a simple polygon
From MaRDI portal
Publication:1178232
DOI10.1016/0020-0190(91)90064-OzbMath0738.68021OpenAlexW2004884735MaRDI QIDQ1178232
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
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)
Related Items (22)
Ray shooting in polygons using geodesic triangulations ⋮ Computing simple paths from given points inside a polygon ⋮ Minimum weight pseudo-triangulations ⋮ Efficient piecewise-linear function approximation using the uniform metric ⋮ Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon ⋮ An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ Piercing pairwise intersecting geodesic disks ⋮ Unnamed Item ⋮ ON GEOMETRIC PATH QUERY PROBLEMS ⋮ Voronoi diagrams for a moderate-sized point-set in a simple polygon ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon ⋮ Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time ⋮ Computing an \(L_1\) shortest path among splinegonal obstacles in the plane ⋮ Computing a geodesic two-center of points in a simple polygon ⋮ On Romeo and Juliet problems: minimizing distance-to-sight ⋮ On Romeo and Juliet Problems: Minimizing Distance-to-Sight. ⋮ Piercing pairwise intersecting geodesic disks by five points ⋮ Shortest zookeeper's routes in simple polygons ⋮ An O\((n\log n)\) algorithm for the zoo-keeper's problem
Cites Work
This page was built for publication: A new data structure for shortest path queries in a simple polygon
