---
res:
  bibo_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:  \r\n1) 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. \r\n2) 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]. \r\n3) 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]. \r\n4) A truly subquadratic-time algorithm and lower bound for Diameter-2
    and Diameter-3 of rectangular boxes (of arbitrary dimension and sizes), respectively.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Timothy M.
      foaf_name: Chan, Timothy M.
      foaf_surname: Chan
  - foaf_Person:
      foaf_givenName: Hsien Chih
      foaf_name: Chang, Hsien Chih
      foaf_surname: Chang
  - foaf_Person:
      foaf_givenName: Jie
      foaf_name: Gao, Jie
      foaf_surname: Gao
  - foaf_Person:
      foaf_givenName: Sándor
      foaf_name: Kisfaludi-Bak, Sándor
      foaf_surname: Kisfaludi-Bak
  - foaf_Person:
      foaf_givenName: Hung
      foaf_name: Le, Hung
      foaf_surname: Le
  - foaf_Person:
      foaf_givenName: Da Wei
      foaf_name: Zheng, Da Wei
      foaf_surname: Zheng
      foaf_workInfoHomepage: http://www.librecat.org/personId=af77956b-e859-11ef-8dc9-d301b898e32f
  bibo_doi: 10.4230/LIPIcs.SoCG.2026.29
  bibo_volume: 367
  dct_date: 2026^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959774185
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_subject:
  - Graph Diameter
  - Geometric Intersection Graphs
  - Unit Ball Graphs
  dct_title: Charting the diameter computation landscape of intersection graphs in
    3D and above@
...