Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs

Computing the diameter in near-quadratic time is possible in several classes of intersection graphs [Chan and Skrepetos 2019], but it is not at all clear if these algorithms are optimal, especially since in the related class of planar graphs, the diameter can be computed in $\widetilde{\mathcal{O}}(n^{5/3})$ time [Cabello 2019, Gawrychowski et al. 2021].

In this work, we (conditionally) rule out sub-quadratic algorithms in several classes of intersection graphs, i.e., algorithms of running time $\mathcal{O}(n^{2-\delta})$ for some $\delta>0$. In particular, there are no sub-quadratic algorithms already for fat objects in small dimensions: unit balls in $\mathbb{R}^3$ or congruent equilateral triangles in $\mathbb{R}^2$. For unit segments and congruent equilateral triangles, we can even rule out strong sub-quadratic approximations already in $\mathbb{R}^2$. It seems that the hardness of approximation may
also depend on dimensionality: for axis-parallel unit hypercubes in $\mathbb{R}^{12}$, distinguishing between diameter 2 and 3 needs quadratic time (ruling out $(3/2-\varepsilon)$- approximations), whereas for
axis-parallel unit squares, we give an algorithm that distinguishes between diameter 2 and 3 in near-linear time.

Note that many of our lower bounds match the best-known algorithms up to sub-polynomial factors.