Fast and Stronger Lower Bounds for Planar Euclidean Shortest Paths
Authors: Stefan Funke, Daniel Koch, Claudius Proissl, Christian Staib, Felix Weitbrecht
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 5 Experiments All our algorithms were implemented in C++, compiled with g++ 11.4.0, and executed on a Ryzen 7950x 16-core Desktop machine with 128GB of RAM running Ubuntu Linux 22.04. For geometric computations we used the CGAL library [The CGAL Project, 2023], in particular its geometry kernel, the exact geometric predicates, as well as the constrained Delaunay triangulation code. Unless stated otherwise, averages and maxima were calculated over 1000 trials. Source code and data sets are available on a companion page [Funke, 2024]. We used several benchmark sets... |
| Researcher Affiliation | Academia | Stefan Funke , Daniel Koch and Claudius Proissl and Christian Staib and Felix Weitbrecht University of Stuttgart, Germany |
| Pseudocode | No | The paper describes algorithms and methods in textual form, for example in Section 3 "Shrunk Graph Creation" and Section 4 "Hub Labeling on Visibility Graphs", but it does not contain any clearly labeled pseudocode or algorithm blocks with structured steps. |
| Open Source Code | No | Source code and data sets are available on a companion page [Funke, 2024]. The URL provided in the reference [Funke, 2024] (https://www.fmi.uni-stuttgart.de/alg/research/) points to a general research group page and not a specific repository for the code described in this paper. |
| Open Datasets | Yes | Source code and data sets are available on a companion page [Funke, 2024]. We used several benchmark sets, some derived from game maps from the repository of [Sturtevant, 2012], an urban environment with building footprints extracted from the Open Street Map project [The Open Street Map Project, 2024], the world s coastlines as also used in [Funke et al., 2024] as well as an arrangement of several Koch snowflakes [Koch, 1904], see Figure 5 for visual depictions of our data sets. |
| Dataset Splits | No | To evaluate the lower bound qualities of our shrunken ESP instances, we chose 1,000 random source-target pairs of the original ESP instance and for each of them computed their shortest path using Polyanya [Cui et al., 2017]. ... For that we considered all benchmark instances, computed the level function based on reach-10k and constructed hub labels. In Table 5, column avg HL time, we report on the average query times for 100 random source-target distance queries using the constructed hub labels. The paper describes how query pairs were chosen for evaluation, but not how a dataset itself was split into distinct training, validation, and test subsets for a model. |
| Hardware Specification | Yes | All our algorithms were implemented in C++, compiled with g++ 11.4.0, and executed on a Ryzen 7950x 16-core Desktop machine with 128GB of RAM running Ubuntu Linux 22.04. |
| Software Dependencies | Yes | All our algorithms were implemented in C++, compiled with g++ 11.4.0, ... For geometric computations we used the CGAL library [The CGAL Project, 2023], in particular its geometry kernel, the exact geometric predicates, as well as the constrained Delaunay triangulation code. The reference for CGAL Project states "5.6 edition, 2023". |
| Experiment Setup | Yes | To evaluate the lower bound qualities of our shrunken ESP instances, we chose 1,000 random source-target pairs... we applied the pure global shrinking strategy. If we lock 2% of the remaining nodes by importance... We evaluated several strategies for determining the level functions on the smallest coastline graph: random chooses as ϕ a random permutation; degree assigns number 1 to n according to increasing degree of the nodes; reach-i determines the hop-based reach value from a set of shortest path trees with i random sources. ... so we will use reach-10k for the following experiments. |