Pith. sign in

REVIEW 3 major objections 5 minor 32 references

An $O(n\log n)$ Algorithm for Single-Source Shortest Paths in Disk Graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that single-source shortest paths in disk graphs can be computed in O(n log n) time, and in fat-triangle intersection graphs in O(n log^2 n) time.

desk verdict Genuine improvement to disk-graph SSSP, but the proof of the load-bearing Lemma 5 has a real gap that needs fixing before the main theorem is trustworthy. read the letter →

arxiv 2506.07571 v1 pith:62VG35O5 submitted 2025-06-09 cs.CG

Mark de Berg , Sergio Cabello This is my paper
classification cs.CG MSC 68U0568R1005C85
keywords diskgraphsfattrianglessingle-sourceshortestpathsgeometricintersectionclique-basedcontractionskipquadtreesshortest-pathtreeBichromaticTesting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that the single-source shortest-path problem on disk graphs—graphs whose vertices are disks and whose edges connect intersecting disks—can be solved in O(n log n) time, and on intersection graphs of fat triangles in O(n $log^{2}$ n) time. The previous best bound for disk graphs was O(n $log^{2}$ n), and the authors state they are not aware of any earlier SSSP algorithm for fat triangles. The method works by building a sparse contracted graph: it partitions the objects into cliques of mutually intersecting objects, replaces each clique by one node, and shows the resulting graph has only O(n log n) edges after arranging the cliques so that no point lies in too many of their unions. If the proof is correct, shortest paths in these geometric graphs can be computed in near-linear time rather than quadratic time.

What carries the argument

The load-bearing objects are the shifted hierarchical grids of Lemma 3, which guarantee that every disk is aligned with one of three grids; skip quadtrees, which organize the objects so that those assigned to the same node can be grouped into O(1) stabbed cliques; and flowers, the unions of the objects in a clique, whose boundary arcs are charged to pairwise non-overlapping fat sectors in Lemma 5. The number of flower-boundary intersections is O(n log n), so the set of all intersecting flower pairs—the edges of the clique-based contraction—can be reported efficiently with a deterministic segment-intersection algorithm. The contraction reduces level-by-level SSSP to a Bichromatic Intersection Testing subroutine, which for disks is answered with an additively weighted Voronoi diagram and for fat triangles with three data structures handling vertex containment, point stabbing, and canonical-chord intersection.

What would settle it

Construct the flowers produced by the clique construction for a small disk set, draw the modified sectors from Lemma 5, and test whether any two sectors from different flowers have overlapping interiors; alternatively, brute-force count boundary-arc intersections across many random and adversarial disk sets and look for a family where the count exceeds a constant times n log n. Any concrete counterexample to sector disjointness would refute the proof as written.

Watch

Extended reading notes

Core claim

At the paper's center is Theorem 9: given n disks in the plane, a shortest-path tree from a specified source disk can be built in O(n log n) time under the real-RAM model with quadtree support; Theorem 16 gives the analogue for fat triangles in O(n $log^{2}$ n) time. The improvement comes from replacing the potentially quadratic intersection graph with a clique-based contraction: the disks are partitioned into stabbed cliques (sets of mutually intersecting disks that share a common point), and two cliques are connected in the contracted graph when their unions, called flowers, intersect. The crucial geometric lemma bounds the number of pairwise intersections of flower boundary arcs by O(n log n) through a charging scheme using pairwise non-overlapping fat sectors, which keeps the whole construction near-linear. A direct corollary is that running the fat-triangle algorithm from every source gives all-pairs shortest paths for fat triangles of arbitrary sizes in O($n^{2}$ $log^{2}$ n) time, improving both the running time and the generality of an earlier all-pairs algorithm.

Load-bearing premise

The proof depends on Lemma 5's claim that the fat sectors built inside different flowers never overlap except at shared arc endpoints; if two such sectors can overlap in their interiors, the O(n log n) bound on flower-boundary intersections, and hence the claimed running time, no longer follows.

Editorial extensions

If this is right

  • For disk graphs, shortest-path trees can now be computed in O(n log n) time, improving the previous O(n log^2 n) bound.
  • For intersection graphs of fat triangles, the paper gives the first known near-linear polylogarithmic SSSP algorithm, with running time O(n log^2 n).
  • Running the fat-triangle algorithm once per source yields all-pairs shortest paths for fat triangles of arbitrary sizes in O(n^2 log^2 n) time, beating the earlier O(n^2 log^4 n) algorithm that required roughly equal-size triangles.
  • The level-by-level framework applies to any class of constant-complexity objects for which a clique-based contraction and a Bichromatic Intersection Testing subroutine exist, and it extends to a multi-source version where the starting set is a collection of sources rather than one source.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the O(n log n) edge bound survives scrutiny, the same sector-charging idea may transfer to other fat objects, such as fat rectangles or convex bodies with bounded aspect ratio, giving near-linear contractions for their intersection graphs.
  • A direct computational check of Lemma 5 on random and adversarial disk sets—building the modified sectors and testing whether any two sectors from different flowers overlap in their interiors—would provide a quick, independent sanity check of the paper's most delicate step.
  • The algorithm's deterministic containment-reporting machinery suggests the result could be implemented with standard computational geometry building blocks, though the hidden constants from quadtrees and Voronoi preprocessing would determine whether the near-linear bound is practical.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper presents an O(n log n) algorithm for the single-source shortest-path (SSSP) problem in disk graphs, improving on the previous O(n log^2 n) bound, and an O(n log^2 n) algorithm for intersection graphs of fat triangles. The approach instantiates Klost's level-by-level framework: it first computes a clique-based contraction of the intersection graph, then uses a Bichromatic Intersection Testing subroutine at each level. The clique construction combines shifted quadtrees and skip quadtrees so that the resulting flowers have logarithmic ply; the edge set of the contraction is computed by reporting boundary-arc intersections and containments among flowers, using a sector-packing argument (Lemma 5) for disks and a similar argument (Lemma 10) for fat triangles. The disk BIT subroutine uses an additively weighted Voronoi diagram; the fat-triangle BIT combines three new data structures for triangle emptiness, point stabbing, and canonical segment intersection queries. The main theorems are Theorem 9 for disk graphs and Theorem 16 for fat triangles.

Significance. If the main claims are correct, this is a substantial improvement: the SSSP problem on disk graphs is brought from O(n log^2 n) to O(n log n), and the paper gives the first near-linear polylogarithmic SSSP algorithm for intersection graphs of fat triangles, with an improved APSP corollary. The algorithmic design is elegant and credits prior work carefully; it uses established tools (shifted quadtrees, skip quadtrees, Voronoi upper envelopes) rather than fitted constants or circular reasoning. The paper also states its model of computation and gives explicit subroutines, which makes the result falsifiable and reproducible in principle. The main weaknesses are proof gaps in the two sector-disjointness lemmas and an overly general summation claim inside the framework theorem; these are load-bearing points that require repair before the paper can be accepted.

major comments (3)
  1. [§3, Lemma 5] The proof of the claim that the sectors in Z_F are pairwise non-overlapping is not valid as written. The triangle inequality yields p∈D′ or p′∈D in the closed sense; since p and p′ are points on ∂F, they may still lie on the boundary of D′ or D, respectively (for instance, as common endpoints of two exposed arcs). The asserted contradiction to 'p and p′ are both points on ∂F' therefore does not follow. This is not a cosmetic issue: Lemma 5 is exactly the step that charges boundary-arc intersections to sector intersections and bounds the total by O(n·ply(F)), which in turn controls the size of the clique-based contraction in Proposition 8 and Theorem 9. The authors should repair this by proving that a proper crossing of the two radial segments forces a point in the strict interior of the other disk (or by treating the boundary/degenerate cases separately), or provide an independent proof of the non-overlap claim.
  2. [§4, Lemma 10] The fat-triangle analogue has the same logical gap. In the crossing argument for the isosceles 'sectors', the statement 'p∈∆, which contradicts that p lies on an external edge' is only valid if p is in the interior of ∆; as written, p could lie on the boundary of ∆ while still being on the external edge of another sector. In addition, the assertion that the external edge of any sector cannot properly intersect an edge of any other sector is stated without proof. Since Lemma 10 underpins Proposition 11 and Theorem 16, this proof needs the same careful treatment of strict containment and boundary cases as Lemma 5.
  3. [§2, Theorem 1] The proof of Theorem 1 claims that the inequality ∑ℓ Tbit(nℓ, |Lℓ|) = O(Tbit(n,n)) follows from Tbit being 'at least linear' and 'at most quadratic'. This is not true in that generality: for example, Tbit(x,y) = x^2/y + x + y is at least linear and at most quadratic on the relevant range, but with nℓ concentrated on a level where |Lℓ| is small, the sum can be Θ(n^2) while Tbit(n,n)=Θ(n). The applications in Sections 3 and 4 use Tbit(nB,nR)=O((nB+nR)log nR) and Tbit(nB,nR)=O((nB+nR)log^2(nB+nR)), which do satisfy the needed summation bound. Please restate the framework theorem with a concrete sufficient hypothesis on Tbit, or prove the summation bound directly for the two BIT subroutines actually used.
minor comments (5)
  1. [§4, Lemma 15] There is a typo in the lemma statement: 'segmwnts' should be 'segments'.
  2. [§3, Lemma 7] The treatment of points on the boundary of disks should be made explicit. The statement says p∉⋃D iff λ(p) lies in the interior of a facet of U; this implicitly handles closed disks, but a sentence clarifying the convention (and how boundary tangencies are treated) would improve readability.
  3. [§4, Lemma 13] The claimed partition of a fat triangle into four semi-canonical triangles is stated in one sentence without proof. Since the rest of the lemma's data structure depends on this decomposition, a brief derivation of why each resulting piece has two canonical edges would be helpful.
  4. [§4, Lemma 14] The statement that a stabbing query can be answered 'in logarithmic time by binary search' over the cone decomposition is terse. Please explain what is searched (presumably the sorted angular order of rays around the apex) and why finding the cone containing the query point determines membership in the flower.
  5. [§4, Observation 12] The case analysis in the proof is quite compressed, especially the last sentence 'In the latter case, ∆′ must have a vertex inside ∆'. Expanding this argument would make the observation easier to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the SSSP algorithm's O(n log n) analysis depends on external geometric lemmas and independently constructed subroutines, not on the target running time or on any fitted or self-referential input.

full rationale

The paper is an algorithmic construction with no fitted constants, no data-fitting step, and no prediction that is defined in terms of the claimed output. The central derivation chain is: (i) a level-by-level SSSP framework (Theorem 1) that reduces the problem to a clique-based contraction and a Bichromatic Intersection Testing subroutine; (ii) a construction of the clique-based contraction via Chan's hierarchical grids and skip quadtrees, with the O(n log n) bound following from Lemma 4 (ply of flowers is O(log n)) and Lemma 5 (boundary-arc intersections are O(n · ply)); and (iii) standard Voronoi-diagram based Bichromatic Intersection Testing for disks. Each ingredient is either proved in the paper from explicit geometric arguments or cited from prior external work (Chan's alignment lemma, Eppstein et al. on skip quadtrees, Balaban's segment-intersection algorithm, Chazelle-Edelsbrunner, upper-envelope techniques). The self-citations (Cabello and Jejčič for unit-disk SSSP) appear only in the historical discussion and are not load-bearing for the new result. The fat-triangle extension similarly builds its own clique-based contraction (Lemma 10, Proposition 11) before using the intersection-testing data structures (Lemmas 13-15); Lemma 14 reuses the paper's own contraction algorithm, but that algorithm was already proven independently, so there is no circular dependency. Even the skeptical issue noted in the reader's take, namely that the proof of sector non-overlap in Lemma 5 may be incomplete, is a correctness risk and not a circularity: a flawed proof of a geometric bound is not the same as deriving the bound from its own assumption. No step equates a prediction to a fit, imports a uniqueness theorem through self-citation, or smuggles in the claimed O(n log n) time as an input. Therefore the appropriate circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No fitted parameters exist in this line of work; every bound is a worst-case running time. The axioms listed are standard results or explicitly stated model choices. The only invented objects are formal algorithmic constructs (cliques, flowers, canonical chords) that are defined in the paper and require no independent external evidence.

assumptions (5)
  • standard math Chan's Lemma 3: three hierarchical grids suffice so every bounded object is 6-aligned with at least one grid.
    Invoked in Section 3 (Finding the cliques) to partition disks or triangles by alignment; if this lemma failed, the O(n log n) clique construction would need more grids and extra log factors.
  • standard math Skip quadtrees can be built in O(n log n) time and have O(log n) depth.
    Used in Section 3 Steps 1 and 2 and in Lemma 14; establishes depth and assignment bounds for the clique construction.
  • standard math The union of the objects forming a flower has linear combinatorial complexity, and fat sectors allow charging intersections to O(ply) per region.
    Used in Lemma 5 and Lemma 10 to bound |B(F)| and the number of boundary arc or segment intersections.
  • domain assumption Real-RAM model with O(1)-time disk intersection and an O(n log n) compressed-quadtree construction primitive.
    Stated in Section 1 under the model of computation; standard for quadtree algorithms.
  • standard math Upper envelopes of planes and convex polyhedron intersection algorithms run in the specified time bounds.
    Used in Lemma 7 for testing points in a union of disks and in Proposition 8 for merging Voronoi diagrams.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An $O(n\log n)$ Algorithm for Single-Source Shortest Paths in Disk Graphs." pith.science (2026). https://pith.science/paper/62VG35O5

@misc{pith2026250607571,
  author       = {Pith},
  title        = {Pith review of: An $O(n\log n)$ Algorithm for Single-Source Shortest Paths in Disk Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/62VG35O5}},
  note         = {Machine review of arXiv:2506.07571}
}
abstract

We prove that the single-source shortest-path problem on disk graphs can be solved in $O(n\log n)$ time, and that it can be solved on intersection graphs of fat triangles in $O(n\log^2 n)$ time.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

32 extracted references · 16 canonical work pages

  1. [1]

    Agarwal, Matthew J

    Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir. Computing depth orders for fat objects and related problems. Comput. Geom. , 5:187--206, 1995. https://doi.org/10.1016/0925-7721(95)00005-8 doi:10.1016/0925-7721(95)00005-8

    work page doi:10.1016/0925-7721(95)00005-8 1995

  2. [2]

    Improved bounds for the union of locally fat objects in the plane

    Boris Aronov, Mark de Berg, Esther Ezra, and Micha Sharir. Improved bounds for the union of locally fat objects in the plane. SIAM J. Comput. , 43(2):543--572, 2014. https://doi.org/10.1137/120891241 doi:10.1137/120891241

    doi:10.1137/120891241 2014

  3. [3]

    Ivan J. Balaban. An optimal algorithm for finding segments intersections. In Proc. 11th Symposium on Computational Geometry ( SoCG ) , pages 211--219, 1995. https://doi.org/10.1145/220279.220302 doi:10.1145/220279.220302

    work page arXiv 1995

  4. [4]

    Shortest paths in intersection graphs of unit disks

    Sergio Cabello and Miha Jej c i c . Shortest paths in intersection graphs of unit disks. Comput. Geom. , 48(4):360--367, 2015. https://doi.org/10.1016/j.comgeo.2014.12.003 doi:10.1016/j.comgeo.2014.12.003

    doi:10.1016/j.comgeo.2014.12.003 2015

  5. [5]

    Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms , 46(2):178--189, 2003. https://doi.org/10.1016/S0196-6774(02)00294-8 doi:10.1016/S0196-6774(02)00294-8

    doi:10.1016/s0196-6774(02)00294-8 2003

  6. [6]

    Timothy M. Chan. A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. J. ACM , 57(3):16:1--16:15, 2010. https://doi.org/10.1145/1706591.1706596 doi:10.1145/1706591.1706596

    arXiv 2010

  7. [7]

    Timothy M. Chan. A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions. Discret. Comput. Geom. , 56(4):860--865, 2016. https://doi.org/10.1007/S00454-016-9785-3 doi:10.1007/S00454-016-9785-3

    work page doi:10.1007/s00454-016-9785-3 2016

  8. [8]

    Chan and Zhengcheng Huang

    Timothy M. Chan and Zhengcheng Huang. Constant-hop spanners for more geometric intersection graphs, with even smaller size. In Proc. 39th International Symposium on Computational Geometry (SoCG) , volume 258 of LIPIcs , pages 23:1--23:16, 2023. https://doi.org/10.4230/LIPICS.SoCG.2023.23 doi:10.4230/LIPICS.SoCG.2023.23

    doi:10.4230/lipics.socg.2023.23 2023

Show all 32 references
  1. [9]

    Chan and Dimitrios Skrepetos

    Timothy M. Chan and Dimitrios Skrepetos. All-pairs shortest paths in unit-disk graphs in slightly subquadratic time. In Seok - Hee Hong, editor, Proc. 27th International Symposium on Algorithms and Computation (ISAAC) , volume 64 of LIPIcs , pages 24:1--24:13, 2016. https://do...

    2016 doi

  2. [10]

    Chan and Dimitrios Skrepetos

    Timothy M. Chan and Dimitrios Skrepetos. All-pairs shortest paths in geometric intersection graphs. J. Comput. Geom. , 10(1):27--41, 2019. https://doi.org/10.20382/JOCG.V10I1A2 doi:10.20382/JOCG.V10I1A2

    2019 doi

  3. [11]

    An optimal algorithm for intersecting three-dimensional convex polyhedra

    Bernard Chazelle. An optimal algorithm for intersecting three-dimensional convex polyhedra. SIAM J. Comput. , 21(4):671--696, 1992. https://doi.org/10.1137/0221041 doi:10.1137/0221041

    1992 doi

  4. [12]

    An optimal algorithm for intersecting line segments in the plane

    Bernard Chazelle and Herbert Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. J. ACM , 39(1):1--54, 1992. https://doi.org/10.1145/147508.147511 doi:10.1145/147508.147511

    1992

  5. [13]

    Bernard Chazelle and Leonidas J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica , 1(2):133--162, 1986. https://doi.org/10.1007/BF01840440 doi:10.1007/BF01840440

    1986 doi

  6. [14]

    Cormen, Charles E

    Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms . The MIT Press, 3rd edition, 2009

    2009

  7. [15]

    van Kreveld, and Mark H

    Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational Geometry: Algorithms and Applications (3rd Edition) . Springer, 2008. https://doi.org/10.1007/978-3-540-77974-2 doi:10.1007/978-3-540-77974-2

    2008 doi

  8. [16]

    Algorithms in Combinatorial Geometry , volume 10 of EATCS Monographs on Theoretical Computer Science

    Herbert Edelsbrunner. Algorithms in Combinatorial Geometry , volume 10 of EATCS Monographs on Theoretical Computer Science . Springer, 1987. https://doi.org/10.1007/978-3-642-61568-9 doi:10.1007/978-3-642-61568-9

    1987 doi

  9. [17]

    Guibas, and Jorge Stolfi

    Herbert Edelsbrunner, Leonidas J. Guibas, and Jorge Stolfi. Optimal point location in a monotone subdivision. SIAM J. Comput. , 15(2):317--340, 1986. https://doi.org/10.1137/0215023 doi:10.1137/0215023

    1986 doi

  10. [18]

    Alon Efrat, Alon Itai, and Matthew J. Katz. Geometry helps in bottleneck matching and related problems. Algorithmica , 31(1):1--28, 2001. https://doi.org/10.1007/S00453-001-0016-8 doi:10.1007/S00453-001-0016-8

    2001 doi

  11. [19]

    Goodrich, and Jonathan Z

    David Eppstein, Michael T. Goodrich, and Jonathan Z. Sun. Skip quadtrees: Dynamic data structures for multidimensional point sets. Int. J. Comput. Geom. Appl. , 18:131--160, 2008. https://doi.org/10.1142/S0218195908002568 doi:10.1142/S0218195908002568

    2008 doi

  12. [20]

    New lower bounds for H opcroft's problem

    Jeff Erickson. New lower bounds for H opcroft's problem. Discret. Comput. Geom. , 16(4):389--418, 1996. https://doi.org/10.1007/BF02712875 doi:10.1007/BF02712875

    1996 doi

  13. [21]

    A sweepline algorithm for V oronoi diagrams

    Steven Fortune. A sweepline algorithm for V oronoi diagrams. Algorithmica , 2:153--174, 1987. https://doi.org/10.1007/BF01840357 doi:10.1007/BF01840357

    1987 doi

  14. [22]

    Algorithms for Fat Objects: Decompositions and Applications

    Chris Gray. Algorithms for Fat Objects: Decompositions and Applications . PhD thesis, TU Eindhoven, 2008. URL: https://pure.tue.nl/ws/portalfiles/portal/3256691/200811208.pdf

    2008

  15. [23]

    Guibas and Jorge Stolfi

    Leonidas J. Guibas and Jorge Stolfi. Primitives for the manipulation of general subdivisions and computation of V oronoi diagrams. ACM Trans. Graph. , 4(2):74--123, 1985. https://doi.org/10.1145/282918.282923 doi:10.1145/282918.282923

    1985

  16. [24]

    Geometric approximation algorithms , volume 173 of Mathematical Surveys and Monographs

    Sariel Har-Peled. Geometric approximation algorithms , volume 173 of Mathematical Surveys and Monographs . American Mathematical Society, 2011. https://doi.org/10.1090/surv/173 doi:10.1090/surv/173

    2011 doi

  17. [25]

    Dynamic planar V oronoi diagrams for general distance functions and their algorithmic applications

    Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Dynamic planar V oronoi diagrams for general distance functions and their algorithmic applications. Discret. Comput. Geom. , 64(3):838--904, 2020. https://doi.org/10.1007/S00454-020-00243-7 doi:10.100...

    2020 doi

  18. [26]

    Kirkpatrick

    David G. Kirkpatrick. Efficient computation of continuous skeletons. In Proc. 20th Annual Symposium on Foundations of Computer Science (FOCS) , pages 18--27. IEEE Computer Society, 1979. https://doi.org/10.1109/SFCS.1979.15 doi:10.1109/SFCS.1979.15

    1979 doi

  19. [27]

    An algorithmic framework for the single source shortest path problem with applications to disk graphs

    Katharina Klost. An algorithmic framework for the single source shortest path problem with applications to disk graphs. Comput. Geom. , 111:101979, 2023. https://doi.org/10.1016/j.comgeo.2022.101979 doi:10.1016/j.comgeo.2022.101979

    2023

  20. [28]

    Nearly optimal planar k nearest neighbors queries under general distance functions

    Chih-Hung Liu. Nearly optimal planar k nearest neighbors queries under general distance functions. SIAM Journal on Computing , 51(3):723--765, 2022. https://doi.org/10.1137/20M1388371 doi:10.1137/20M1388371

    2022 doi

  21. [29]

    Lectures on Discrete Geometry , volume 212 of Graduate Texts in Mathematics

    Jir \' Matousek. Lectures on Discrete Geometry , volume 212 of Graduate Texts in Mathematics . Springer, 2002

    2002

  22. [30]

    A fast planar partition algorithm, II

    Ketan Mulmuley. A fast planar partition algorithm, II . J. ACM , 38(1):74--103, 1991. https://doi.org/10.1145/102782.102785 doi:10.1145/102782.102785

    1991

  23. [31]

    On bounded leg shortest paths problems

    Liam Roditty and Michael Segal. On bounded leg shortest paths problems. Algorithmica , 59(4):583--600, 2011. https://doi.org/10.1007/S00453-009-9322-3 doi:10.1007/S00453-009-9322-3

    2011 doi

  24. [32]

    Willard and George S

    Dan E. Willard and George S. Lueker. Adding range restriction capability to dynamic data structures. J. ACM , 32(3):597--617, 1985. https://doi.org/10.1145/3828.3839 doi:10.1145/3828.3839

    1985

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.