On reverse shortest paths in geometric proximity graphs

DOI10.1016/j.comgeo.2023.102053zbMath1527.05047OpenAlexW4386616789MaRDI QIDQ6092309

Pankaj K. Agarwal, Micha Sharir, Matthew J. Katz

Publication date: 23 November 2023

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2023.102053

zbMATH Keywords

range searchinggeometric optimizationsemi-algebraic setsproximity graphsreverse shortest paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Distance in graphs (05C12)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal partition trees
• On bounded leg shortest paths problems
• Range searching with efficient hierarchical cuttings
• Reverse shortest path problem for unit-disk graphs
• Unit disk graphs
• Randomized optimal algorithm for slope selection
• On an instance of the inverse shortest paths problem
• On range searching with semialgebraic sets
• Unit disk graph recognition is NP-hard
• Computation of the reverse shortest-path problem
• Efficient algorithms for approximating polygonal chains
• Reverse shortest path problem in weighted unit-disk graphs
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Near-optimal algorithms for shortest paths in weighted unit-disk graphs
• Shortest paths in intersection graphs of unit disks
• Multilevel polynomial partitions and simplified range searching
• Selecting distances in the plane
• Complexity of some inverse shortest path lengths problems
• Computing Maximally Separated Sets in the Plane
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• An Expander-Based Approach to Geometric Optimization
• Simplex Range Searching and Its Variants: A Review
• Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs
• All-pairs shortest paths in geometric intersection graphs
• ON ENUMERATING AND SELECTING DISTANCES
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• On Range Searching with Semialgebraic Sets. II
• Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications
• Approximation and Online Algorithms
• Algorithms in real algebraic geometry
• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION

This page was built for publication: On reverse shortest paths in geometric proximity graphs