Towards space efficient two-point shortest path queries in a polygonal domain

DOI10.4230/LIPICS.SOCG.2024.17MaRDI QIDQ6895889zbMATH OpenFDO

Authors Sarita de Berg, Tillmann Miltzow, Frank Staals

Publication date 24 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2024.17

zbMATH Keywords

data structuregeodesic distancepolygonal domain

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A divide-and-conquer algorithm for two-point L1 shortest path queries in polygonal domains
• A new algorithm for Euclidean shortest paths in the plane
• Almost tight upper bounds for lower envelopes in higher dimensions
• Almost tight upper bounds for vertical decompositions in four dimensions
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Compact Oracles for Approximate Distances Around Obstacles in the Plane
• Computational geometry. Algorithms and applications.
• Computing Envelopes in Four Dimensions with Applications
• Computing minimum length paths of a given homotopy class
• Cutting hyperplanes for divide-and-conquer
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• scientific article; zbMATH DE number 1305410 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 7030514 (Why is no real title available?)
• scientific article; zbMATH DE number 910885 (Why is no real title available?)
• scientific article; zbMATH DE number 7759291 (Why is no real title available?)
• scientific article; zbMATH DE number 7788389 (Why is no real title available?)
• scientific article; zbMATH DE number 7788587 (Why is no real title available?)
• Improved dynamic geodesic nearest neighbor searching in a simple polygon
• Kinetic geodesic Voronoi diagrams in a simple polygon
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• New applications of random sampling in computational geometry
• ON GEOMETRIC PATH QUERY PROBLEMS
• On range searching with semialgebraic sets
• Optimal algorithm for geodesic nearest-point Voronoi diagrams in simple polygons
• Optimal Point Location in a Monotone Subdivision
• Optimal shortest path queries in a simple polygon
• Querying two boundary points for shortest paths in a polygonal domain
• Shortest Path Queries Among Weighted Obstacles in the Rectilinear Plane
• Shortest Path Queries in Polygonal Domains
• The geodesic diameter of polygonal domains
• THE VISIBILITY COMPLEX
• Two-point L₁ shortest path queries in the plane

Cited in

(3)

• Link diameter, radius and 2-point link distance queries in polygonal domains
• Towards space efficient two-point shortest path queries in a polygonal domain
• Realizing metric spaces with convex obstacles

This page was built for publication: Towards space efficient two-point shortest path queries in a polygonal domain

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