On bounded leg shortest paths problems
From MaRDI portal
Publication:633848
DOI10.1007/s00453-009-9322-3zbMath1211.68474OpenAlexW3137365097MaRDI QIDQ633848
Publication date: 30 March 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-009-9322-3
Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (11)
Reverse shortest path problem for unit-disk graphs ⋮ Reverse shortest path problem in weighted unit-disk graphs ⋮ An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs ⋮ On reverse shortest paths in geometric proximity graphs ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition ⋮ Near-optimal algorithms for shortest paths in weighted unit-disk graphs ⋮ Unnamed Item ⋮ Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs. ⋮ Shortest paths in intersection graphs of unit disks ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Halfspace range search: An algorithmic application of k-sets
- Applications of a semi-dynamic convex hull algorithm
- Efficient partition trees
- Dynamic Euclidean minimum spanning trees and extrema of binary functions
- A sparse graph almost as good as the complete graph on points in \(k\) dimensions
- A new approach to all-pairs shortest paths on real-weighted graphs
- Approximating geometric bottleneck shortest paths
- Fly Cheaply: On the Minimum Fuel Consumption Problem
- Dynamic planar convex hull operations in near-logarithmic amortized time
- Undirected single-source shortest paths with positive integer weights in linear time
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries
- On the convex layers of a planar set
- Decomposable searching problems I. Static-to-dynamic transformation
- New Techniques for Exact and Approximate Dynamic Closest-Point Problems
- Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications
This page was built for publication: On bounded leg shortest paths problems
