Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Fulltext
Final published version, 854 KB, PDF document
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.
Original language | English |
---|---|
Title of host publication | 38th International Symposium on Computational Geometry, SoCG 2022 |
Editors | Xavier Goaoc, Michael Kerber |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2022 |
Article number | 21 |
ISBN (Electronic) | 9783959772273 |
DOIs | |
Publication status | Published - 2022 |
Event | 38th International Symposium on Computational Geometry, SoCG 2022 - Berlin, Germany Duration: 7 Jun 2022 → 10 Jun 2022 |
Conference
Conference | 38th International Symposium on Computational Geometry, SoCG 2022 |
---|---|
Land | Germany |
By | Berlin |
Periode | 07/06/2022 → 10/06/2022 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 224 |
ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:
© Karl Bringmann, Sndor Kisfaludi-Bak, Marvin Knnemann, Andr Nusser, and Zahra Parsaeian; licensed under Creative Commons License CC-BY 4.0
- Geometric Intersection Graph, Graph Diameter, Hardness in P, Hyperclique Detection, Orthogonal Vectors
Research areas
ID: 342674106