# Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs

Karl Bringmann*, Sándor Kisfaludi-Bak, Marvin Künnemann, André Nusser, Zahra Parsaeian

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

12 Lataukset (Pure)

## Abstrakti

We initiate the study of diameter computation in geometric intersection graphs from the fine-grained complexity perspective. A geometric intersection graph is a graph whose vertices correspond to some shapes in d-dimensional Euclidean space, such as balls, segments, or hypercubes, and whose edges correspond to pairs of intersecting shapes. The diameter of a graph is the largest distance realized by a pair of vertices in the graph. Computing the diameter in near-quadratic time is possible in several classes of intersection graphs [Chan and Skrepetos 2019], but it is not at all clear if these algorithms are optimal, especially since in the related class of planar graphs the diameter can be computed in Oe(n5/3) time [Cabello 2019, Gawrychowski et al. 2021]. In this work we (conditionally) rule out sub-quadratic algorithms in several classes of intersection graphs, i.e., algorithms of running time O(n2-d) for some d > 0. In particular, there are no sub-quadratic algorithms already for fat objects in small dimensions: unit balls in R3 or congruent equilateral triangles in R2. For unit segments and congruent equilateral triangles, we can even rule out strong sub-quadratic approximations already in R2. It seems that the hardness of approximation may also depend on dimensionality: for axis-parallel unit hypercubes in R12, distinguishing between diameter 2 and 3 needs quadratic time (ruling out (3/2-e)- approximations), whereas for axis-parallel unit squares, we give an algorithm that distinguishes between diameter 2 and 3 in near-linear time. Note that many of our lower bounds match the best known algorithms up to sub-polynomial factors. Ultimately, this fine-grained perspective may enable us to determine for which shapes we can have efficient algorithms and approximation schemes for diameter computation.

Alkuperäiskieli Englanti 38th International Symposium on Computational Geometry, SoCG 2022 Xavier Goaoc, Michael Kerber Schloss Dagstuhl-Leibniz-Zentrum für Informatik 1-16 16 978-3-95977-227-3 https://doi.org/10.4230/LIPIcs.SoCG.2022.21 Julkaistu - 1 kesäk. 2022 A4 Artikkeli konferenssijulkaisuussa International Symposium on Computational Geometry - Berlin, SaksaKesto: 7 kesäk. 2022 → 10 kesäk. 2022Konferenssinumero: 38

### Julkaisusarja

Nimi Leibniz International Proceedings in Informatics, LIPIcs Schloss Dagstuhl-Leibniz-Zentrum für Informatik 224 1868-8969

### Conference

Conference International Symposium on Computational Geometry SoCG Saksa Berlin 07/06/2022 → 10/06/2022

## Sormenjälki

Sukella tutkimusaiheisiin 'Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.