2026-09-05T11:38:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26443 2026-08-27T14:39:36Z ddc:004 open_access

Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane Chan, Timothy M. Chang, Hsien-Chih Gao, Jie Kisfaludi-Bak, Sándor Le, Hung Zheng, Da Wei String graphs Fine-grained complexity 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]. We 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: 1) 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. 2) 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. 3) 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]. 4) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan and Hsien-Chih Chang and Jie Gao and Sándor Kisfaludi-Bak and Hung Le and Da Wei Zheng 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.54 urn:nbn:de:0030-drops-264432 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.54 eng https://creativecommons.org/licenses/by/4.0/legalcode