Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above

Our first result is a separation between unit (hyper)cubes and unit balls: Diameter-3 for unit balls is hard, whereas Diameter-3 for unit cubes admits a truly subquadratic-time algorithm.

Our lower bound for Diameter-3 of unit balls is by reducing from Diameter-2 of sparse tripartite graphs $G=(A\cup B\cup C,E)$, which is quadratic hard under the OV hypothesis. Our first idea for the reduction would be to create a unit ball for each vertex in $A\cup B\cup C$, as well as a unit ball for each edge in $E$. We encode edges in the original graph $G$ by intersection: a vertex $u\in A\cup B\cup C$ is incident to an edge $uv\in E$ if and only if the unit balls corresponding to $u$ and $uv$ intersect. Then a length-2 path $a\to b\to c$ in $G$ will correspond to a length-4 path $⦇a⦈\to ⦇ab⦈\to ⦇b⦈\to ⦇bc⦈\to ⦇c⦈$ in the intersection graph, where $⦇x⦈$ is the unit ball corresponding to (a vertex or an edge) $x$. With this idea, we could obtain hardness of Diameter-4. To obtain a lower bound for Diameter-3, we do not create unit balls for the middle set of vertices $B$; the path would then be $⦇a⦈\to ⦇ab⦈\to ⦇bc⦈\to ⦇c⦈$. The difficulty is to guarantee that $⦇ab⦈$ only intersects $⦇bc⦈$, not $⦇\tilde{b}c⦈$ for some other vertex $\tilde{b}\in B$; in the Diameter-4 case, this is enforced by the ball $⦇b⦈$. Here, we achieve the guarantee by introducing an angle parameter $\delta$ to control the intersections of the balls and prevent unwanted edges from being added. See Section 2.

The algorithms for Diameter-2 and 3 for unit cubes in Theorem 3 are perhaps most interesting. First, we show that the VC-dimension of the 2- and 3-neighborhoods of 3D unit cubes is bounded by a constant. Here we depart from existing techniques for the 2D case [14, 11, 8], which rely on the non-planarity of $K_5$. In a small region, unit cubes behave like orthants, and so the intersection between unit cubes corresponds to a dominance relation. We divide the sequence of dominance relations on the length-2 and length-3 path into a number of special cases, bound the VC-dimension of each by 1 or 2 via direct arguments, and then bound the overall VC-dimension by combining subsystems together. See Section 3.1 and Section 4.1 for details.

Our VC-dimension bound, in combination with existing techniques [8], is enough to imply truly-subquadratic-time algorithms for Diameter-2 and Diameter-3, but because of large constants, the running time would be awfully close to quadratic (about $O(n^{1.99999992})$ for Diameter-3). We further build on the proof ideas to give ultra efficient algorithms: In the case of Diameter-2, because the subsystems from various cases actually all have VC-dimension 1, we are able to use orthogonal range searching, in combination with divide-and-conquer, to achieve near-linear time. (Large constants appear in the logarithmic factors, instead of in the main polynomial factor.) For Diameter-3, because the subsystems from various cases actually turn out to be special kinds of 2-dimensional systems corresponding to pseudoline arrangements, we are able to use known range searching techniques, in combination with a grid approach, to achieve a more reasonable running time $\tilde{O}(n^{2-1/13})$. (We find it surprising that pseudolines turn out to be relevant for a problem about 3D unit cubes!) The technical details are intricate, as we need to work with abstract pseudolines that are only implicitly represented via certain oracles. See Section 3 and §4 of full paper for details.

Our constant bound on the VC-dimension of the 2- and 3-neighborhoods of 3D unit cube graphs suggests an intriguing open question of independent interest to combinatorial geometers: do $r$-neighborhoods similarly have bounded VC-dimension for all constant $r>3$?

Combining with [8], Conjecture 4 would imply that unit-cube graphs of constant diameter admit a truly-subquadratic-time algorithm for computing diameter, which is a natural class of intersection graphs motivated by Question 1.

Next, we show that Diameter-3 is quadratic hard for unit hypercubes in 4D. Therefore, there is no longer a meaningful separation between unit hypercubes and unit balls in dimension 4. When the dimension is even higher, say at least 6D, we can get hardness results for Diameter-2, under the $3$-uniform $6$-hyperclique (3H6) hypothesis or combinatorial 4-clique (combK4) hypothesis, by refining Bringmann et al.’s previous proof [5] which required 12 dimensions. We also rule out near-linear time combinatorial algorithms in 4D under the combinatorial boolean matrix multiplication (BMM) hypothesis. See Section 2 of full paper for details.

In 2D, the intersection graphs of (non-unit) squares admit a truly subquadratic-time algorithm for computing the diameter (of any value) [8]. In 3D, we show that for (non-unit) cubes, Diameter-3 is quadratic-hard; this, along with the algorithms in Theorem 3, gives a separation between cubes and their unit counterparts. In contrast, we show that Diameter-2 of (non-unit) cubes is solvable in truly-subquadratic time. Even for the more general case of 3D boxes, we also obtain a truly-subquadratic-time algorithm. (Note that this result is new even for 2D rectangles!) Instead of relying on VC-dimension, this subquadratic algorithm uses a different, grid-based approach. Grid-based approaches have been used before for solving other problems about boxes [7, 10], but one challenge arises from the fact that 3D boxes (or cubes) have quadratic union complexity, unlike 3D unit cubes or orthants. We show that in the case of diameter 2, some of the sides are irrelevant and some boxes can actually be replaced by orthants. See Section 5 of full paper for details.

Our collection of results for many types of objects in 2D (in the companion paper [9]) and higher-dimensional cases reinforces the same pattern: truly subquadratic-time algorithms are mostly for graphs with bounded VC dimension. We conjecture that these are special cases of a broader phenomenon.

Here, by low-complexity, we mean that the geometric object has constant description complexity. A positive resolution of Conjecture 8 would provide a powerful algorithmic tool for solving the diameter problem on geometric intersection graphs. A non-trivial test case for Conjecture 8 is (non-unit) disks in 2D: the distance VC dimension is at most 4 [11] whereas currently there is no known truly-subquadratic algorithm even for Diameter-2.

It is tempting to strengthen Conjecture 8 to an “if and only if” statement; however, our truly-subquadratic algorithm for Diameter-2 of boxes in Theorem 7 provides a counter-example: the intersection graphs of diameter 2 for boxes and rectangles have unbounded VC-dimension. (For proof of unbounded VC-dimension, see the full paper for details)

Throughout this paper, let $G=(V,E)$ be a geometric intersection graph on $n$ geometric objects $𝒪$. The input will be $𝒪$ and the graph will be implicit. We use $d(u,v)$ to denote the distance between two vertices $u,v\in V$ in $G$. We denote the 1-hop neighborhood of a vertex $v\in V$ by $N[v]$, and the $r$-neighborhood ball of $v$ by $N^r[v]≔\{u\in V:d(u,v)\le r\}$.

For a set system $(U,ℱ)$, define $Sh(n)$$:={\max }_{|S|=n}|\{S\cap F:F\in ℱ\}|$. The shatter dimension of the set system is the minimum $d$ such that $Sh(n)=O(n^d)$. By the Sauer-Shelah Lemma [20, 21], if the VC-dimension is $d$, then the shatter dimension is $d$. The converse partially holds: if the shatter dimension is $d$, then the VC-dimension is $O(d\log d)$.

Consider points $p,p^{\prime }\in P$. Suppose $\{p\}$ and $\{p^{\prime }\}$ are both shattered (by ${𝒮}_{⊲⊲}(P,Q,R)$). Then there exist $r,r^{\prime }\in R$ with $p\in N_{⊲⊲}^2[r]$, $p^{\prime }\notin N_{⊲⊲}^2[r]$, $p^{\prime }\in N_{⊲⊲}^2[r^{\prime }]$, $p\notin N_{⊲⊲}^2[r^{\prime }]$. Let $q,q^{\prime }\in Q$ with $p{⊲}_{1}q{⊲}_{2}r$ and $p^{\prime }{⊲}_1{q}^{\prime }{⊲}_2{r}^{\prime }$.

For any ${⊲}_i$, we define ${⊲}_{ix}$, ${⊲}_{iy}$, and ${⊲}_{iz}$ to be the $x$-, $y$-, and $z$-coordinate dominance relation, respectively. Because $P$ and $Q$ are $x$- and $y$-separated, we already know that $p{⊲}_{1x}{q}^{\prime }$, $p{⊲}_{1y}{q}^{\prime }$, and $p^{\prime }{⊲}_{1x}q$, $p^{\prime }{⊲}_{1y}q$. Note that $p{⊲}_{1z}{q}^{\prime }$ or $p^{\prime }{⊲}_{1z}q$, because otherwise, we must have ${⊲}_{1z}\ne \top$ and $q^{\prime }{⊲}_{1z}p{⊲}_{1z}q{⊲}_{1z}{p}^{\prime }{⊲}_{1z}{q}^{\prime }$: a contradiction. Thus, $p{⊲}_1{q}^{\prime }$ or $p^{\prime }{⊲}_{1}q$, implying $p\in N_{⊲⊲}^2[r^{\prime }]$ or $p^{\prime }\in N_{⊲⊲}^2[r]$. $◀$

We then handle the case when $P$ and $R$ are separated along all 3 axes.

Without loss of generality, say $P\subset {(-\mathrm{\infty },0)}^3$ and $R\subset {(0,\mathrm{\infty })}^3$. Consider the following 6 set systems of the form ${𝒮}_{⊲⊲}(P,Q\cap \mathrm{\Lambda },R)$, where $\mathrm{\Lambda }$ can be one of

Each set system has VC-dimension at most 1 by Lemma 13 (or symmetric variants).

Each set in ${𝒮}_{⊲⊲}(P,Q,R)$ can be expressed as the union of 6 sets (one of each) from these 6 set systems (since a point $q\in Q$ must has two positive coordinates or two negative coordinates). So, the number of distinct sets in ${𝒮}_{⊲⊲}(P,Q,R)$ is at most $O({|P|}^6)$. $◀$

It remains to reduce the general case to the case when $P$ and $R$ are separated along all 3 axes. We accomplish this by a simple grid idea:

Build a (non-uniform) grid formed by the $x$-, $y$-, and $z$-coordinates of all the points of $P$. The grid has $O({|P|}^3)$ cells. For each grid cell interior $\gamma$, consider the 8 octants at an arbitrary point inside $\gamma$; for each such octant $\tau$, the set system ${𝒮}_{⊲⊲}(P\cap \tau ,Q,R\cap \gamma )$ has shatter dimension at most 6 by Lemma 14. For each $r\in R\cap \gamma$, the set $N_{⊲⊲}^2[r]$ is the union of 8 sets (one of each) from the set systems for the 8 octants. So for each $\gamma$, the number of distinct sets in $\{N_{⊲⊲}^2[r]:r\in R\cap \gamma \}$ is $O({({|P|}^6)}^8)$, summing across all cells gives $|\{N_{⊲⊲}^2[r]:r\in R\}|=O({|P|}^3\cdot {({|P|}^6)}^8)$. $◀$

We can now bound the shatter dimension for unit cubes.

Fix $\alpha =({\alpha }_P,{\alpha }_Q)\in {({\mathbb{Z}}^3)}^2$ with ${\Vert {\alpha }_P-{\alpha }_Q\Vert }_{\mathrm{\infty }}\le 1$. For $p\in {\alpha }_P+{(0,1)}^3$ and $q\in {\alpha }_Q+{(0,1)}^3$, $⟦p⟧$ intersects $⟦q⟧$ iff $p-{\alpha }_P{⊲}_{1}q-{\alpha }_Q$, where we define ${⊲}_{1x}$ to be ${\succ }_x$ if $x({\alpha }_Q)=x({\alpha }_P)+1$, and ${\prec }_x$ if $x({\alpha }_Q)=x({\alpha }_P)-1$, and $\top$ if $x({\alpha }_Q)=x({\alpha }_P)$; we define ${⊲}_{1y}$ and ${⊲}_{1z}$ in the same way. Similarly, for $q\in {\alpha }_Q+{(0,1)}^3$ and $r\in {(0,1)}^3$, $⟦q⟧$ intersects $⟦r⟧$ iff $q-{\alpha }_Q{⊲}_{2}r$ for some generalized dominance relation ${⊲}_2$. Define the set system ${𝒮}_{\alpha }≔{𝒮}_{⊲⊲}(P\cap ({\alpha }_P+{(0,1)}^3)-{\alpha }_P,(Q\cap ({\alpha }_Q+{(0,1)}^3))-{\alpha }_Q,R)$.

Each set $N^2[r]$ is the union of at most ${27}^2$ sets (one of each) from the set systems ${𝒮}_{\alpha }$ for the at most ${27}^2$ choices of $\alpha$. By Lemma 15, we have $|\{N^2[r]:r\in R\}|=O({({|P|}^{51})}^{{27}^2})$. $◀$

Build a uniform grid of side length 1. For each grid cell ${\alpha }_R+{(0,1)}^3$ (with ${\alpha }_R\in {\mathbb{Z}}^3$), the number of different $N^2[r]$ sets over all $r\in R\cap ({\alpha }_R+{(0,1)}^3)$ is $O({|P\cap ({\alpha }_R+{(-2,3)}^3)|}^{37179})$ by Lemma 16. Since each point $p\in P$ belongs to $O(1)$ number of expanded cells ${\alpha }_R+{(-2,3)}^3$, the sum over all ${\alpha }_R$ is $O({|P|}^{37179})$. $◀$

In the interest of simplicity, we have not optimized the above constant (which admittedly is quite large, but fortunately will not matter in our final algorithm).

Suppose $p{⊲}_{j}q$ iff $p{⊲}_{jx}q$ and $p{⊲}_{jy}q$ and $p{⊲}_{jz}q$ with ${⊲}_{jx}\in \{{\prec }_x,{\succ }_x,\top \}$, ${⊲}_{jy}\in \{{\prec }_y,{\succ }_y,\top \}$, and ${⊲}_{jz}\in \{{\prec }_z,{\succ }_z,\top \}$. We may assume that ${⊲}_{1x}\ne \top$ (because if not, we can shift all the $x$-coordinates of $P$ sufficiently far downward and replace ${⊲}_{1x}$ with ${\prec }_x$), and similarly, all other ${⊲}_{jx},{⊲}_{jy},{⊲}_{jz}$ are not $\top$. We first prove the following property:

Property: Let $p,p^{\prime }\in P$ and $s,s^{\prime }\in S$. If $p\in N_{⊲⊲⊲}^3[s]$, $p^{\prime }\in N_{⊲⊲⊲}^3[s^{\prime }]$, $p\notin N_{⊲⊲⊲}^3[s^{\prime }]$, $p^{\prime }\notin N_{⊲⊲⊲}^3[s]$, then $p{\prec }_y{p}^{\prime }$ implies $s^{\prime }{◀}_{y}s$, where ${◀}_y\in \{{\prec }_y,{\succ }_y\}$ is a relation determined solely from the choices of ${⊲}_1,{⊲}_2,{⊲}_3$.

Proof: Let $q,q^{\prime }\in Q$ and $r,r^{\prime }\in R$ with $p{⊲}_{1}q{⊲}_{2}r{⊲}_{3}s$ and $p^{\prime }{⊲}_1{q}^{\prime }{⊲}_2{r}^{\prime }{⊲}_3{s}^{\prime }$. We may assume neither $p{⊲}_1{q}^{\prime }$ nor $p^{\prime }{⊲}_{1}q$, because otherwise, $p\in N_{⊲⊲⊲}^3[s^{\prime }]$ or $p^{\prime }\in N_{⊲⊲⊲}^3[s]$. Because $P$ and $Q$ are $x$-separated, we already know $p{⊲}_{1x}{q}^{\prime }$ and $p^{\prime }{⊲}_{1x}q$. So, there are two remaining possibilities: (i) $p{⊲}_{1y}q{⊲}_{1y}{p}^{\prime }{⊲}_{1y}{q}^{\prime }$ and $p^{\prime }{⊲}_{1z}{q}^{\prime }{⊲}_{1z}p{⊲}_{1z}q$, or (ii) $p^{\prime }{⊲}_{1y}{q}^{\prime }{⊲}_{1y}p{⊲}_{1y}q$ and $p{⊲}_{1z}q{⊲}_{1z}{p}^{\prime }{⊲}_{1z}{q}^{\prime }$. (See Figure 1.)

Define ${◀}_{1z}\in \{{\prec }_z,{\succ }_z\}$ to be ${⊲}_{1z}$ iff ${⊲}_{1y}$ is ${\prec }_y$. Then $p{\prec }_y{p}^{\prime }$ implies $q^{\prime }{◀}_{1z}q$.

Similarly, we may assume neither $q{⊲}_2{r}^{\prime }$ nor $q^{\prime }{⊲}_{2}r$, because otherwise, $p\in N_{⊲⊲⊲}^3[s^{\prime }]$ or $p^{\prime }\in N_{⊲⊲⊲}^3[s]$. Because $Q$ and $R$ are $y$-separated, $q{⊲}_{2y}{r}^{\prime }$ and $q^{\prime }{⊲}_{2y}r$. There are two remaining possibilities: (i) $q{⊲}_{2z}r{⊲}_{2z}{q}^{\prime }{⊲}_{2z}{r}^{\prime }$ and $q^{\prime }{⊲}_{2x}{r}^{\prime }{⊲}_{2x}q{⊲}_{2x}r$, or (ii) $q^{\prime }{⊲}_{2z}{r}^{\prime }{⊲}_{2z}q{⊲}_{2z}r$ and $q{⊲}_{2x}r{⊲}_{2x}{q}^{\prime }{⊲}_{2x}{r}^{\prime }$.

Define ${◀}_{2x}\in \{{\prec }_x,{\succ }_x\}$ to be ${⊲}_{2x}$ iff ${⊲}_{2z}$ is ${◀}_{1z}$. Then $q^{\prime }{◀}_{1z}q$ implies $r{◀}_{2x}{r}^{\prime }$.

Similarly (and lastly), we may assume neither $r{⊲}_3{s}^{\prime }$ nor $r^{\prime }{⊲}_{3}s$, because otherwise, $p\in N_{⊲⊲⊲}^3[s^{\prime }]$ or $p^{\prime }\in N_{⊲⊲⊲}^3[s]$. Because $R$ and $S$ are $z$-separated, $r{⊲}_{3z}{s}^{\prime }$ and $r^{\prime }{⊲}_{3z}s$. There are two remaining possibilities: (i) $r{⊲}_{3x}s{⊲}_{3x}{r}^{\prime }{⊲}_{3x}{s}^{\prime }$ and $r^{\prime }{⊲}_{3y}{s}^{\prime }{⊲}_{3y}r{⊲}_{3y}s$, or (ii) $r^{\prime }{⊲}_{3x}{s}^{\prime }{⊲}_{3x}r{⊲}_{3x}s$ and $r{⊲}_{3y}s{⊲}_{3y}{r}^{\prime }{⊲}_{3y}{s}^{\prime }$.

Define ${◀}_y\in \{{\prec }_y,{\succ }_y\}$ to be ${⊲}_{3y}$ iff ${⊲}_{3x}$ is ${◀}_{2x}$. Then $r{◀}_{2x}{r}^{\prime }$ implies $s^{\prime }{◀}_{y}s$. $\mathrm{\square }$

Now, consider 3 points $p,p^{\prime },p^{\prime \prime }\in P$, with $p{\prec }_y{p}^{\prime }{\prec }_y{p}^{\prime \prime }$. Suppose $\{p,p^{\prime \prime }\}$ and $\{p^{\prime }\}$ are both shattered. Then there exist $s,s^{\prime }\in S$ with $p,p^{\prime \prime }\in N_{⊲⊲⊲}^3[s]$, $p^{\prime }\notin N_{⊲⊲⊲}^3[s]$, $p^{\prime }\in N_{⊲⊲⊲}^3[s^{\prime }]$, $p,p^{\prime \prime }\notin N_{⊲⊲⊲}^3[s^{\prime }]$. Applying the property twice yields $s^{\prime }{◀}_{y}s$ and $s{◀}_y{s}^{\prime }$: a contradiction. $◀$

Consider 2 points $p,p^{\prime }\in P$. Suppose $\{p\}$ and $\{p^{\prime }\}$ are both shattered. Then there exist $s,s^{\prime }\in S$ with $p\in N_{⊲⊲⊲}^3[s]$, $p^{\prime }\notin N_{⊲⊲⊲}^3[s]$, $p^{\prime }\in N_{⊲⊲⊲}^3[s^{\prime }]$, $p\notin N_{⊲⊲⊲}^3[s^{\prime }]$. Let $q,q^{\prime }\in Q$ and $r,r^{\prime }\in R$ with $p{⊲}_{1}q{⊲}_{2}r{⊲}_{3}s$ and $p^{\prime }{⊲}_1{q}^{\prime }{⊲}_2{r}^{\prime }{⊲}_3{s}^{\prime }$.

For (a), $p{⊲}_{1x}{q}^{\prime }$, $p{⊲}_{1y}{q}^{\prime }$, and $p^{\prime }{⊲}_{1x}q$, $p^{\prime }{⊲}_{1y}{q}^{\prime }$ by the separation assumptions. Note that $p{⊲}_{1z}{q}^{\prime }$ or $p^{\prime }{⊲}_{1z}q$, because otherwise, $q^{\prime }{⊲}_{1z}p{⊲}_{1z}q{⊲}_{1z}{p}^{\prime }{⊲}_{1z}{q}^{\prime }$: a contradiction. Thus, $p{⊲}_1{q}^{\prime }$ or $p^{\prime }{⊲}_{1}q$, implying $p\in N_{⊲⊲⊲}^3[s^{\prime }]$ or $p^{\prime }\in N_{⊲⊲⊲}^3[s]$.

Claims (b) and (c) follow from a similar argument. $◀$

We now handle the case when $P$ and $S$ are separated along all 3 axes, by invoking the previous cases some constant number of times:

Denote ${ℝ}_{+}$ and ${ℝ}_{-}$ to be $(0,\mathrm{\infty })$ and $(-\mathrm{\infty },0)$, respectively. Without loss of generality, say $P\subset {ℝ}_{-}^3$ and $S\subset {ℝ}_{+}^3$. Consider the following 15 set systems.