arxiv: 2604.23171 · v1 · submitted 2026-04-25 · 💻 cs.CG · cs.DS

Recognition: unknown

Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs

Mark de Berg , Bart M.P. Jansen , Jeroen S.K. Lamme

Authors on Pith no claims yet

Pith reviewed 2026-05-08 07:02 UTC · model grok-4.3

classification 💻 cs.CG cs.DS

keywords single-source shortest pathsintersection graphspseudodisksunion complexitydiameter approximationr-clusteringcomputational geometrysubquadratic algorithms

0 comments

The pith

Union complexity of plane objects yields single-source shortest paths in their unweighted intersection graphs in O(U(n) polylog n) expected time.

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

The paper establishes that single-source shortest paths in unweighted intersection graphs of n constant-complexity plane objects can be solved in O(U(n) polylog n) expected time whenever the objects have union complexity U(n). For pseudodisks this produces an O(n 2^{α(n)} log² n) algorithm, and for locally fat objects an O(λ_{s+2}(n) 2^{O(log* n)} log² n) algorithm. These bounds extend the range of geometric graphs that admit near-linear SSSP far beyond the previously known cases of similarly sized fat convex objects. The same framework yields an algorithm that computes the diameter of arbitrary pseudodisk graphs up to an additive error of 2 in Õ(n^{2-1/14}) expected time, along with a distance oracle using O(n^{2-1/13}) space and constant query time.

Core claim

For any class of n constant-complexity objects in the plane whose union complexity is U(n), single-source shortest paths in the unweighted intersection graph can be computed in O(U(n) polylog n) expected time. In particular, arbitrary pseudodisks admit an O(n 2^{α(n)} log² n) algorithm and locally fat objects admit an O(λ_{s+2}(n) 2^{O(log* n)} log² n) algorithm. The diameter of arbitrary pseudodisks can be approximated within additive error 2 in Õ(n^{2-1/14}) expected time by means of a star-based r-clustering of the intersection graph.

What carries the argument

A general reduction from single-source shortest paths on the intersection graph to the union complexity U(n) of the objects, instantiated via a star-based r-clustering for pseudodisks.

If this is right

SSSP on pseudodisk graphs runs in O(n 2^{α(n)} log² n) expected time.
SSSP on locally fat object graphs runs in O(λ_{s+2}(n) 2^{O(log* n)} log² n) expected time.
Diameter of pseudodisk graphs can be computed up to additive error 2 in Õ(n^{2-1/14}) expected time.
A distance oracle for pseudodisk graphs uses O(n^{2-1/13}) space and answers queries in O(1) time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The star-based r-clustering may extend to other geometric intersection graphs that admit low-complexity separators.
The O(U(n) polylog n) SSSP bound could be combined with existing techniques to obtain faster all-pairs distances when U(n) is near-linear.
Subquadratic almost-exact diameter may open the door to similar approximation results for other global graph properties such as radius or center.

Load-bearing premise

The objects are of constant descriptive complexity and the input intersection graph is unweighted, with the running time depending only on how small the union complexity U(n) is.

What would settle it

A family of pseudodisks whose union complexity is O(n) but whose single-source shortest paths require quadratic time in the worst case, or an instance where the diameter cannot be approximated within additive error 2 in o(n²) time.

read the original abstract

We study SINGLE-SOURCE SHORTEST PATH (SSSP) on unweighted intersection graphs whose node set corresponds to a set of $n$ constant-complexity objects in the plane. We prove SSSP can be solved in $O(U(n)\ \mathrm{polylog}\,n)$ expected time for any class of objects whose union complexity is $U(n)$. In particular, we obtain an $O(n 2^{\alpha(n)}\log^2 n)$ algorithm for arbitrary pseudodisks, and an $O(\lambda_{s+2}(n)2^{O(\log^* n)} \log^2 n)$ algorithm for locally fat objects. This significantly extends the class of objects for which SSSP can be solved in $O(n\ \mathrm{polylog}\, n)$ time: so far, $O(n\ \mathrm{polylog}\, n)$ SSSP algorithms were not even known for pseudodisks that are fat and convex and similarly-sized. Our second result concerns the DIAMETER problem, which asks for the maximum distance between any two nodes in a graph. Even for intersection graphs, near-quadratic algorithms are difficult to obtain, and the $O(n^2\ \mathrm{polylog}\, n)$ running time that follows from our SSSP algorithm is the first near-quadratic running time for such general classes of intersection graphs. Obtaining subquadratic running time is even more challenging. We prove that the diameter of a set of arbitrary pseudodisks can be computed almost exactly, namely up to an additive error of 2, in $\tilde{O}(n^{2-1/14})$ expected time. This generalizes and speeds up a recent algorithm by Chang, Gao, and Le~(SoCG 2024) that works for similarly-sized disks (or similarly-sized pseudodisks that are fat and satisfy a strong monotonicity assumption) and runs in $\tilde{O}(n^{2-1/18})$ time. To this end, we develop a so-called star-based $r$-clustering for intersection graphs of pseudodisks, which is interesting in its own right. Our star-based $r$-clustering can also be used to obtain an almost exact distance oracle for pseudodisks that uses $O(n^{2-1/13})$ storage and has $O(1)$ query time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper reduces SSSP to union complexity for planar object graphs, getting near-linear time for arbitrary pseudodisks plus a subquadratic almost-exact diameter via new clustering.

read the letter

The core result is a general SSSP algorithm that runs in O(U(n) polylog n) expected time for unweighted intersection graphs of constant-complexity planar objects, where U(n) is the union complexity. For arbitrary pseudodisks this gives O(n 2^α(n) log² n), and they get a comparable bound for locally fat objects. They also introduce a star-based r-clustering that lets them compute diameter up to additive error 2 in Õ(n^{2-1/14}) expected time, plus a distance oracle with O(n^{2-1/13}) space and O(1) queries. This extends earlier work that needed fatness, convexity, and similar sizes, and it slightly improves the exponent from the recent disk paper. The reduction itself looks clean: it guides a search using boundary complexity of the union, and the specific bounds follow from standard combinatorial results on U(n) without extra assumptions. The clustering construction is presented as reusable and seems to avoid the usual pitfalls in geometric graph algorithms. No load-bearing circularity or hidden parameters show up in the claims. The main limitations are that the times are expected and that the bounds degrade if U(n) is large, but those are explicit and standard for this setting. Everything stays within known union-complexity literature rather than inventing new combinatorial facts. This is worth reading for anyone working on geometric intersection graphs or shortest-path problems in the plane. The techniques are concrete enough to be picked up or adapted. It deserves peer review; the framework is general and the applications are sharp enough to justify referee time.

Referee Report

0 major / 3 minor

Summary. The paper studies single-source shortest paths (SSSP) and the diameter problem on unweighted intersection graphs of n constant-complexity objects in the plane. It proves SSSP can be solved in O(U(n) polylog n) expected time for any class with union complexity U(n), yielding O(n 2^α(n) log² n) for arbitrary pseudodisks and O(λ_{s+2}(n) 2^{O(log* n)} log² n) for locally fat objects. For diameter, it computes the value up to additive error 2 in Õ(n^{2-1/14}) expected time for pseudodisks via a new star-based r-clustering, which also yields an almost-exact distance oracle with O(n^{2-1/13}) space and O(1) query time.

Significance. If the results hold, the work is significant because it substantially extends the range of geometric intersection graphs admitting near-linear SSSP algorithms, removing prior requirements for fatness, convexity, or similar sizes. The general reduction to union complexity U(n) is a clean, reusable abstraction with no free parameters. The star-based r-clustering is a novel technical contribution that enables the first subquadratic almost-exact diameter result for arbitrary pseudodisks and improves the exponent over Chang-Gao-Le (SoCG 2024). These elements are likely to find further applications in geometric graph problems.

minor comments (3)

Abstract: the term 'locally fat objects' is used without a one-sentence definition or pointer to the formal definition; adding this would improve readability for readers outside the immediate sub-area.
Diameter section: the improvement from the prior 2-1/18 exponent to 2-1/14 is stated but not accompanied by a brief comparison of the clustering parameters that produce the gain; a short sentence would clarify the technical advance.
Notation: the star-based r-clustering is introduced as 'interesting in its own right'; a dedicated definition paragraph early in that section would help readers track the subsequent applications to diameter and oracles.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our paper and the recommendation of minor revision. The referee's summary correctly reflects our main results on SSSP via union complexity and the almost-exact diameter algorithm for pseudodisks using star-based r-clustering.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The central result reduces SSSP to O(U(n) polylog n) expected time via a new algorithmic framework that directly exploits the boundary complexity of the union of objects. This bound is then instantiated using independently established combinatorial results on U(n) for pseudodisks (O(n 2^α(n))) and locally fat objects (O(λ_{s+2}(n))), without any fitted parameters, self-definitional loops, or load-bearing self-citations. The star-based r-clustering for the diameter result generalizes prior work by unrelated authors and introduces no reductions to the paper's own inputs. All steps are externally verifiable combinatorial and algorithmic constructions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard assumptions from computational geometry (constant-complexity objects, union complexity bounds) and graph algorithms; no new free parameters or invented entities are introduced.

axioms (1)

domain assumption Objects have constant complexity and the intersection graph is unweighted
Invoked throughout the abstract to bound union complexity and enable the SSSP and diameter results.

pith-pipeline@v0.9.0 · 5759 in / 1231 out tokens · 77215 ms · 2026-05-08T07:02:18.315387+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages

[1]

XX:16 OntheDoublingDimensionandthePerimeterofGeodesicallyConvexSetsinFatPolygons 4 Glencora Borradaile, Hung Le, and Christian Wulff-Nilsen

doi: 10.1137/120891241. 2 Boris Aronov, Mark de Berg, and Leonidas Theocharous. A clique-based separator for intersection graphs of geodesic disks in $\mathbb {R}ˆ2$.Algorithmica, 87(12):1997–2017, 2025.doi:10.1007/S00453-025-01337-5. 3 Julien Basch, Leonidas J. Guibas, and G. D. Ramkumar. Reporting red - blue intersections between two sets of connected l...

work page doi:10.1137/120891241 1997
[2]

11 Timothy M

doi:10.4230/LIPICS.ISAAC.2016.24. 11 Timothy M. Chan and Dimitrios Skrepetos. Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs. InProc. 34th International Symposium on Computational Geometry (SoCG), volume 99, pages 24:1–24:13, 2018.doi:10.4230/LIPIcs.SoCG.2018.24. 12 Timothy M. Chan and Dimitrios Skrepetos. All-pairs shortest ...

work page doi:10.4230/lipics.isaac.2016.24 2016
[3]

20 Mark de Berg, Bart M

doi:10.1007/ 978-3-540-77974-2. 20 Mark de Berg, Bart M. P. Jansen, and Jeroen S. K. Lamme. Star-based separators for intersection graphs of c-colored pseudo-segments. In Ho-Lin Chen, Wing-Kai Hon, and Meng- Tsung Tsai, editors,Proc. 36th International Symposium on Algorithms and Computation (ISAAC), LIPIcs, pages 12:1–12:16, 2025.doi:10.4230/LIPICS.ISAAC...

work page doi:10.4230/lipics.isaac.2025.12 2025
[4]

doi:10.4230/LIPICS.ISAAC.2021.25. M. de Berg, B.M.P. Jansen, and J.S.K. Lamme 31 25 Jie Gao and Li Zhang. Well-separated pair decomposition for the unit-disk graph metric and its applications.SIAM Journal on Computing, 35(1):151–169,

work page doi:10.4230/lipics.isaac.2021.25 2021
[5]

26 Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, and Oren Weimann

doi:10.1137/ S0097539703436357. 26 Pawel Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, and Oren Weimann. Voronoi diagrams on planar graphs, and computing the diameter in deterministic õ(n5/3) time.SIAM J. Comput., 50(2):509–554, 2021.doi:10.1137/18M1193402. 27 Sariel Har-Peled and Micha Sharir. Online point location in planar arrangements and its a...

work page doi:10.1137/18m1193402 2021
[6]

2015 , month = nov, journal =

35 Seth Pettie. Sharp bounds on davenport-schinzel sequences of every order.J. ACM, 62(5):36:1– 36:40, 2015.doi:10.1145/2794075. 36 Micha Sharir. The clarkson-shor technique revisited and extended.Comb. Probab. Comput., 12(2):191–201, 2003.doi:10.1017/S0963548302005527. 37 Micha Sharir and Pankaj K. Agarwal.Davenport-Schinzel sequences and their geometric...

work page doi:10.1145/2794075 2015
[7]

Shortest-path queries in static networks.ACM Comput

38 Christian Sommer. Shortest-path queries in static networks.ACM Comput. Surv., 46(4):45:1– 45:31, 2014.doi:10.1145/2530531. 39Endre Szemerédi. On a problem of Davenport and Schinzel.Acta Arith., 25:213–224,

work page doi:10.1145/2530531 2014
[8]

41 Christian Wulff-Nilsen

doi:10.1145/1044731.1044732. 41 Christian Wulff-Nilsen. Constant time distance queries in planar unweighted graphs with subquadratic preprocessing time.Computational Geometry, 46(7):831–838, 2013.doi:doi. org/10.1016/j.comgeo.2012.01.016

work page doi:10.1145/1044731.1044732 2013