What question did this study set out to answer?

This research aims to explore and improve the computation of graph diameter in three and higher dimensions, especially for intersection graphs.

May 29, 2026Open Access

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

Key Points

This research aims to explore and improve the computation of graph diameter in three and higher dimensions, especially for intersection graphs.
Developed a subquadratic-time algorithm for determining Diameter-3 of unit cubes in 3D.
Established lower bounds for Diameter-3 of unit balls under the Orthogonal Vector hypothesis.
Created a near-linear-time algorithm for Diameter-2 of unit cubes in 3D.
Presented the first subquadratic-time algorithm for Diameter-3 of unit cubes in 3D.
Achieved a truly subquadratic-time lower bound for Diameter-3 of unit balls under the OV hypothesis.
Developed a near-linear-time algorithm for Diameter-2 of unit cubes in 3D.

Abstract

Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case Duraj et al., 2024; Hsien-Chih Chang et al., 2024; Chan et al., 2025 where truly subquadratic-time algorithms were given for simple objects such as unit-disks and (axis-aligned) squares. However, in three or higher dimensions, there is no known truly subquadratic-time algorithm for any intersection graph of non-trivial objects, even basic ones such as unit balls or (axis-aligned) unit cubes. This was partially explained by the pioneering work of Bringmann et al. Karl Bringmann et al., 2022 which gave several truly subquadratic lower bounds, notably for unit balls or unit cubes in 3D when the graph diameter Δ is at least Ω(log n), hinting at a pessimistic outlook for the complexity of the diameter problem in higher dimensions. In this paper, we substantially extend the landscape of diameter computation for objects in three and higher dimensions, giving a few positive results. Our highlighted findings include: 1) A truly subquadratic-time algorithm for deciding if the diameter of unit cubes in 3D is at most 3 (Diameter-3 hereafter), the first algorithm of its kind for objects in 3D or higher dimensions. Our algorithm is based on a novel connection to pseudolines, which is of independent interest. 2) A truly subquadratic time lower bound for Diameter-3 of unit balls in 3D under the Orthogonal Vector (OV) hypothesis, giving the first separation between unit balls and unit cubes in the small diameter regime. Previously, computing the diameter for both objects was known to be quadratic hard when the diameter is Ω(log n) Karl Bringmann et al., 2022. 3) A near-linear-time algorithm for Diameter-2 of unit cubes in 3D, generalizing the previous result for unit squares in 2D Karl Bringmann et al., 2022. 4) A truly subquadratic-time algorithm and lower bound for Diameter-2 and Diameter-3 of rectangular boxes (of arbitrary dimension and sizes), respectively.

Mark Helpful

Bookmark

Relay

View Full Paper