2026-07-20T15:08:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8741 2024-03-06T10:42:32Z ddc:004 open_access

On the Complexity of Closest Pair via Polar-Pair of Point-Sets David, Roee C. S., Karthik Laekhanukit, Bundit Contact dimension Sphericity Closest Pair Fine-Grained Complexity Every graph G can be represented by a collection of equi-radii spheres in a d-dimensional metric Delta such that there is an edge uv in G if and only if the spheres corresponding to u and v intersect. The smallest integer d such that G can be represented by a collection of spheres (all of the same radius) in Delta is called the sphericity of G, and if the collection of spheres are non-overlapping, then the value d is called the contact-dimension of G. In this paper, we study the sphericity and contact dimension of the complete bipartite graph K_{n,n} in various L^p-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Roee David and Karthik C. S. and Bundit Laekhanukit 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.28 urn:nbn:de:0030-drops-87412 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.28 eng https://creativecommons.org/licenses/by/3.0/legalcode