---
res:
  bibo_abstract:
  - "Computing the diameter of the intersection graphs of objects is a basic problem
    in computational geometry. Previous works showed that the complexity of computing
    the diameter mainly depends on the object types: for unit disks and squares in
    2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while
    for other objects, including unit segments and equilateral triangles in 2D or
    unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic
    time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al.,
    2022]. \r\nWe undertake a comprehensive study of computing the diameter of geometric
    intersection graphs for various types of objects. We discover many new irregularities,
    showing that the landscape is extremely nuanced: the source of hardness is a combination
    of the object type, the true diameter value, and how the objects intersect with
    each other. Our highlighted results for the 2D case include:  \r\n1) The diameter
    of non-degenerate, axis-aligned line segments can be computed in truly subquadratic
    time. Previous hardness result [Bringmann et al., 2022] for line segments applies
    only to degenerate instances. On the other hand, for the degenerate case, we show
    that a truly subquadratic time algorithm exists when the true diameter is constant.
    \r\n2) An almost-linear-time algorithm for unit-square graphs of constant diameter.
    Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation
    assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent
    barrier. \r\n3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk
    graph is at most 2. This improves upon the recent algorithm with running time
    Õ(n^{2-1/9}) [Chan et al., 2025]. \r\n4) Deciding if the diameter of intersection
    graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard
    under fine-grained complexity assumptions. Previous lower bounds [Bringmann et
    al., 2022] only hold when deciding if diameter is at most 3.  Our findings are
    presented in a pair of papers. This paper focuses solely on the 2D case, while
    the companion paper is devoted to higher-dimensional cases.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Timothy M.
      foaf_name: Chan, Timothy M.
      foaf_surname: Chan
    orcid: 0000-0002-8093-0675
  - foaf_Person:
      foaf_givenName: Hsien-Chih
      foaf_name: Chang, Hsien-Chih
      foaf_surname: Chang
    orcid: 0000-0001-6714-7988
  - foaf_Person:
      foaf_givenName: Jie
      foaf_name: Gao, Jie
      foaf_surname: Gao
    orcid: 0000-0001-5083-6082
  - foaf_Person:
      foaf_givenName: Sándor
      foaf_name: Kisfaludi-Bak, Sándor
      foaf_surname: Kisfaludi-Bak
    orcid: 0000-0002-6856-2902
  - foaf_Person:
      foaf_givenName: Hung
      foaf_name: Le, Hung
      foaf_surname: Le
    orcid: 0000-0001-8223-9944
  - 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.ICALP.2026.54
  bibo_volume: 374
  dct_date: 2026^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959774284
  dct_language: eng
  dct_publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik@
  dct_subject:
  - String graphs
  - Fine-grained complexity
  - Theory of computation → Computational geometry
  dct_title: Charting the landscape of diameter computation on geometric intersection
    graphs in the plane@
...