---
OA_place: publisher
OA_type: gold
_id: '22004'
abstract:
- lang: eng
  text: "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."
acknowledgement: "Timothy M. Chan: Supported by NSF grant CCF-2224271.\r\nHsien-Chih
  Chang: Supported by NSF CAREER award CCF-2443017.\r\nJie Gao: Supported by NSF DMS-2220271,
  DMS-2311064, IIS-2229876, CCF-2118953, CNS-2515159.\r\nSándor Kisfaludi-Bak: Supported
  by the Research Council of Finland, Grant 363444.\r\nHung Le: Supported by an NSF
  grant CCF-2517033 and an NSF CAREER Award CCF-2237288. Da Wei Zheng: This project
  has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982.
  For open access purposes, the author has applied a CC BY public copyright license
  to any author-accepted manuscript version arising from this submission."
alternative_title:
- LIPIcs
article_number: 29:1-29:15
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Timothy M.
  full_name: Chan, Timothy M.
  last_name: Chan
- first_name: Hsien Chih
  full_name: Chang, Hsien Chih
  last_name: Chang
- first_name: Jie
  full_name: Gao, Jie
  last_name: Gao
- first_name: Sándor
  full_name: Kisfaludi-Bak, Sándor
  last_name: Kisfaludi-Bak
- first_name: Hung
  full_name: Le, Hung
  last_name: Le
- first_name: Da Wei
  full_name: Zheng, Da Wei
  id: af77956b-e859-11ef-8dc9-d301b898e32f
  last_name: Zheng
citation:
  ama: 'Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the diameter
    computation landscape of intersection graphs in 3D and above. In: <i>42nd International
    Symposium on Computational Geometry</i>. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik; 2026. doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2026.29">10.4230/LIPIcs.SoCG.2026.29</a>'
  apa: 'Chan, T. M., Chang, H. C., Gao, J., Kisfaludi-Bak, S., Le, H., &#38; Zheng,
    D. W. (2026). Charting the diameter computation landscape of intersection graphs
    in 3D and above. In <i>42nd International Symposium on Computational Geometry</i>
    (Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2026.29">https://doi.org/10.4230/LIPIcs.SoCG.2026.29</a>'
  chicago: Chan, Timothy M., Hsien Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung
    Le, and Da Wei Zheng. “Charting the Diameter Computation Landscape of Intersection
    Graphs in 3D and Above.” In <i>42nd International Symposium on Computational Geometry</i>,
    Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href="https://doi.org/10.4230/LIPIcs.SoCG.2026.29">https://doi.org/10.4230/LIPIcs.SoCG.2026.29</a>.
  ieee: T. M. Chan, H. C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng,
    “Charting the diameter computation landscape of intersection graphs in 3D and
    above,” in <i>42nd International Symposium on Computational Geometry</i>, New
    Brunswick, NJ, United States, 2026, vol. 367.
  ista: 'Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting
    the diameter computation landscape of intersection graphs in 3D and above. 42nd
    International Symposium on Computational Geometry. SoCG: Symposium on Computational
    Geometry, LIPIcs, vol. 367, 29:1-29:15.'
  mla: Chan, Timothy M., et al. “Charting the Diameter Computation Landscape of Intersection
    Graphs in 3D and Above.” <i>42nd International Symposium on Computational Geometry</i>,
    vol. 367, 29:1-29:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026,
    doi:<a href="https://doi.org/10.4230/LIPIcs.SoCG.2026.29">10.4230/LIPIcs.SoCG.2026.29</a>.
  short: T.M. Chan, H.C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:,
    42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2026.
conference:
  end_date: 2026-06-05
  location: New Brunswick, NJ, United States
  name: 'SoCG: Symposium on Computational Geometry'
  start_date: 2026-06-02
corr_author: '1'
das_tickbox: '0'
date_created: 2026-06-14T22:01:44Z
date_published: 2026-05-27T00:00:00Z
date_updated: 2026-06-22T08:37:44Z
day: '27'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.SoCG.2026.29
external_id:
  arxiv:
  - '2603.21790'
file:
- access_level: open_access
  checksum: ffff03934cc182757d6db82d88f896e6
  content_type: application/pdf
  creator: dernst
  date_created: 2026-06-22T08:34:11Z
  date_updated: 2026-06-22T08:34:11Z
  file_id: '22114'
  file_name: 2026_LIPIcSSoCG_Chan.pdf
  file_size: 918197
  relation: main_file
  success: 1
file_date_updated: 2026-06-22T08:34:11Z
has_accepted_license: '1'
intvolume: '       367'
keyword:
- Graph Diameter
- Geometric Intersection Graphs
- Unit Ball Graphs
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
publication: 42nd International Symposium on Computational Geometry
publication_identifier:
  eissn:
  - 1868-8969
  isbn:
  - '9783959774185'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Charting the diameter computation landscape of intersection graphs in 3D and
  above
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 367
year: '2026'
...